The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915729239965696 |
|---|---|
| author | Rahat, Md. Tanzeem Hasan, Md. Manzurul |
| author_facet | Rahat, Md. Tanzeem Hasan, Md. Manzurul |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08958 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach Rahat, Md. Tanzeem Hasan, Md. Manzurul Data Structures and Algorithms 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$. |
| title | The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.08958 |