The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach

Given two sequences $A[1..n]$ and $B[1..m]$ over a totally ordered alphabet, the \emph{Longest Common Bitonic Subsequence} (LCBS) problem asks for a longest common subsequence that is strictly increasing up to a single peak element and strictly decreasing thereafter (allowing either phase to be empty). The only explicitly documented approach evaluates a quadratic dynamic program over the full $n\times m$ grid, which is prohibitive on large inputs. We present two exact algorithms. First, we give a simple $\Theta(nm)$-time baseline that computes LCBS by combining a longest common increasing subsequence (LCIS) computation on $(A,B)$ with a second LCIS computation on the reversed inputs, and then maximizing $INC(i,j)+DEC(i,j)-1$ over all common peaks. The method is constructive via parent pointers. Second, we develop an \emph{instance-sensitive} algorithm whose running time depends on the number $\mathcal{M}$ of matching pairs $(i,j)$ with $A[i]=B[j]$. We view matches as vertices of a dominance-ordered poset and compute the increasing and decreasing halves by two 2D dominance DP passes supported by orthogonal range-maximum data structures, followed by a linear peak scan. With a standard 2D range tree (or equivalent), this yields $O(\mathcal{M}\log^{2}\mathcal{M} + \mathcal{M} + (n+m)\log(n+m))$ time and $O(\mathcal{M}\log \mathcal{M})$ space, and it improves over the dense baseline whenever $M\log^2 M\ll nm$.

• Publication year

  2025

• Venue

  Unknown venue

• Publication date

  2025-11-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2511.08958
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem

  2020cited by this paper
• A sub-quadratic algorithm for the longest common increasing subsequence problem

  2019cited by this paper
• Multivariate Fine-Grained Complexity of Longest Common Subsequence

  2018cited by this paper
• Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

  2017influential reference
• Tight Hardness Results for LCS and Other Sequence Similarity Measures

  2015influential reference
• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

  2015cited by this paper
• On the generalized constrained longest common subsequence problems

  2011cited by this paper
• THE REPRESENTATIONS OF THE SYMMETRIC GROUP

  2010cited by this paper
• Algorithms for computing variants of the longest common subsequence problem

  2006cited by this paper
• A fast algorithm for computing a longest common increasing subsequence

  2005cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• Introduction to algorithms

  1996cited by this paper
• A fast algorithm for computing longest common subsequences

  1977cited by this paper
• Longest Increasing and Decreasing Subsequences

  1961cited by this paper

• No citing papers are available for this paper.