{"ID":2842601,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.08958","arxiv_id":"2511.08958","title":"The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach","abstract":"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 $Θ(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$.","short_abstract":"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 explici...","url_abs":"https://arxiv.org/abs/2511.08958","url_pdf":"https://arxiv.org/pdf/2511.08958v2","authors":"[\"Md. Tanzeem Rahat\",\"Md. Manzurul Hasan\"]","published":"2025-11-12T04:02:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}