[Model] LongestCommonSubsequence

[zazabap]

Motivation

Foundational string problem underlying diff/version control, bioinformatics (DNA/protein alignment), and data compression. Poly-time for 2 strings via DP, but NP-hard for $k$ strings. Has known reductions to ILP and SAT. Garey & Johnson SR10. This problem is also the core of the git diff.

Definition

Name: LongestCommonSubsequence
Reference: Garey & Johnson, 1979 (SR10); Maier, 1978

Given a finite alphabet $\Sigma$ and a set of $k$ strings $R = {s_1, \ldots, s_k}$ over $\Sigma$, find a longest string $w$ that is a subsequence of every $s_i \in R$.

A string $w$ is a subsequence of $s$ if $w$ can be obtained by deleting zero or more characters from $s$ without changing the order of the remaining characters.

Variables

• Count: $m$ (length of the shortest string in $R$; upper bound on solution length)
• Per-variable domain: $\Sigma$ (alphabet symbols)
• Meaning: $w_j$ is the $j$-th character of the common subsequence $w$

Schema (data type)

Type name: LongestCommonSubsequence

Field	Type	Description
strings	Vec<Vec<u8>>	The input strings $R = {s_1, \ldots, s_k}$

Problem Size

Metric	Expression	Description
num_strings	$k$	Number of input strings
total_length	$\sum_i \lvert s_i \rvert$	Sum of all string lengths

Complexity

• Two strings: $O(mn)$ via dynamic programming (Wagner & Fischer, 1974)
• $k$ strings: NP-hard (Maier, 1978)
• Approximation: Not approximable within $n^{1/4-\varepsilon}$ for any $\varepsilon > 0$; approximable within $O(m / \log m)$ where $m = \min_i |s_i|$

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming, through a new LCS → ILP rule issue (to be filed).

Bruteforce: enumerate all $2^m$ subsequences of the shortest string $s_1$, check each against all other strings, return the longest common one.

Example Instance

$k = 3$ strings over alphabet $\Sigma = {A, B, C, D}$:

String	Value
$s_1$	ABCDAB
$s_2$	BDCABA
$s_3$	BCADBA

Optimal solution: $w$ = BCAB, length 4.

Verification ($w$ is a subsequence of each $s_i$):

String	Matched positions	Trace
ABCDAB	1, 2, 4, 5	ABCDAB
BDCABA	0, 2, 3, 4	BDCABA
BCADBA	0, 1, 2, 4	BCADBA

Note: pairwise LCS lengths are 4, 4, and 5 respectively — the 3-string LCS is harder than any pairwise LCS. For $k = 2$ this problem is solvable in $O(mn)$ time, but the $k$-string generalization is NP-hard.

[isPANN]

Closing as duplicate — this problem is covered by the Garey & Johnson extraction (P161 LongestCommonSubsequence, G&J Appendix A8, SR10). The extracted reference issue in references/Garey&Johnson/issues/models/P161_longest_common_subsequence.md provides a comprehensive definition from the original source.

[GiggleLiu]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in reduction graph; strong motivation
Non-trivial	✅ Pass	Distinct input structure and constraints from all 23 existing problems
Correctness	⚠️ Warn	Core NP-hardness (Maier 1978) verified; approximation bounds unsourced
Well-written	⚠️ Warn	Variables section inconsistent with brute-force encoding; approximation claims need citations

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. LongestCommonSubsequence does not exist in the codebase (confirmed via pred show). The reduction graph currently has 23 problem types — none deal with string/sequence comparison. The motivation is strong: foundational problem in bioinformatics, diff/version control, and data compression, classified as Garey & Johnson SR10.

Minor note: no concrete reduction rules are planned yet (LCS → ILP is mentioned as "to be filed"). The problem would initially be an orphan node in the reduction graph. Consider filing the LCS → ILP rule issue concurrently to ensure graph connectivity.

Non-trivial

Pass. LCS has a genuinely novel input structure (a set of strings over a finite alphabet) that is completely different from all existing problems. The existing categories are graph, formula, set, algebraic, and misc — none handle subsequence/string problems. The feasibility constraint (candidate must be a subsequence of every input string) and objective (maximize length) are both distinct from every existing problem.

Correctness

Warn. Core claims verified, but approximation bounds could not be independently confirmed.

Claim	Status	Details
NP-hard for k strings (Maier 1978)	✅ Verified	Paper "The Complexity of Some Problems on Subsequences and Supersequences," JACM 25(2):322–336. Confirms NP-completeness.
Garey & Johnson SR10	✅ Plausible	SR = Storage and Retrieval; LCS is a standard GJ problem. Consistent with known classifications.
O(mn) DP for 2 strings (Wagner & Fischer 1974)	⚠️ Imprecise	Wagner & Fischer's paper is "The String-to-String Correction Problem" (JACM 21(1):168–173), which solves edit distance, not LCS directly. LCS is mentioned as an application. The O(mn) LCS DP is a standard result but is more commonly considered folklore or attributed to multiple sources.
Not approximable within n^{1/4−ε}	❓ Unverified	No citation given. The well-known result (Jiang & Li, SICOMP 1995) shows n^{1−ε} inapproximability via Max-Clique reduction, but this assumes unbounded alphabet (
Approximable within O(m / log m)	❓ Unverified	No citation given. Recent work shows O(n^{0.4})-approximation in linear time for two strings (Rubinstein et al., ICALP 2021 / ACM TALG 2023). The O(m / log m) ratio for k strings could not be confirmed.

Recommendations

• Add citations for the two approximation claims or remove them.
• Consider attributing the 2-string DP to the standard textbook reference (Cormen et al., CLRS) rather than Wagner & Fischer.
• For the best-known exact algorithm for the k-string case: the issue should specify a concrete time bound (e.g., O(n^k) via k-dimensional DP for fixed k, or a parameterized bound) with a citation, as required by the template's Complexity section.

Well-written

Warn. The issue is well-structured and mostly complete, but has several items that would impede implementation:

Variables section — encoding mismatch:
The Variables section says per-variable domain is Σ (alphabet symbols), with w_j being the j-th character of the common subsequence. However:

1. The brute-force method described uses binary selection from the shortest string (2^m subsequences of s1), implying dims() = vec![2; m] with binary domain.
2. The Σ-domain encoding implies dims() = vec![|Σ|; m], but doesn't address variable-length solutions — the LCS length is unknown and ≤ m. How are "unused" positions encoded?

Recommendation: Align the Variables section with the brute-force encoding: m binary variables (one per character of the shortest string), where 1 = include, 0 = exclude. This naturally fits the Problem trait and matches the described solver.

Missing k-string complexity bound:
The Complexity section gives O(mn) for two strings but only says "NP-hard" for k strings. The template expects a best-known exact algorithm with a specific time bound and citation. For fixed k, the DP runs in O(n^k) time; for variable k, an exponential bound should be stated.

Unsourced approximation claims:
The approximation section has no citations. Both claims (hardness and algorithm) need references.

Minor items:

• Symbol n used in approximation section but never defined (n vs m vs string lengths)
• The naming LongestCommonSubsequence is fine — it follows the universal literature convention, analogous to how TravelingSalesman is used instead of MinimumTravelingSalesman
• Example is well-constructed: 3 strings, non-trivial, fully verified with position traces ✓
• Schema is clean and implementable ✓

Recommendations

• Fix the Variables section to use binary encoding (include/exclude from shortest string)
• Add a complexity bound for the k-string exact algorithm with citation
• Add citations for all approximation claims
• Define all symbols (n, m, k) in a consistent notation section

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem with concrete use cases and planned reductions
Non-trivial	✅ Pass	Distinct input structure (strings) unlike any existing problem
Correctness	⚠️ Warn	Maier 1978 verified; Wagner & Fischer 1974 is about edit distance, not LCS; approximation bound uncited
Well-written	⚠️ Warn	Variables encoding doesn't map cleanly to Problem trait; missing specific complexity bound for declare_variants!

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Problem does not exist in the codebase (pred show LongestCommonSubsequence fails). Motivation is strong: diff/version control, bioinformatics, data compression — all concrete use cases. The issue mentions planned reductions (LCS → ILP via issue #110, LCS → SAT). Brute-force solver path identified. Pass.

Non-trivial

LCS operates on sequences/strings — a fundamentally different input structure from all 23 existing problems (which use graphs, formulas, sets, matrices, or miscellaneous structures). The feasibility constraint (subsequence of all input strings) and objective (maximize length) are genuinely distinct. Not isomorphic to or a variant of any existing problem. Pass.

Correctness

Maier, 1978 — Verified. "The Complexity of Some Problems on Subsequences and Supersequences", JACM 25(2), 322–336. Proves k-string LCS is NP-hard. ✓

Wagner & Fischer, 1974 — This paper ("The String-to-String Correction Problem", JACM 21(1)) is about edit distance, not LCS directly. While LCS length can be derived from edit distance (LCS = (|a| + |b| - edit_dist) / 2 for unit costs), the standard O(mn) DP for LCS is a distinct algorithm. It's more commonly presented as a straightforward DP application without a single primary attribution, though Hirschberg (1975) is often cited for the space-efficient variant. The attribution is not wrong per se, but is imprecise.

Garey & Johnson SR10 — Plausible but unverified (SR = Storage and Retrieval category). The references.md doesn't list SR-category problems. Not contradicted by any known fact.

Approximation claim ("not approximable within $n^{1/4-\varepsilon}$") — No citation provided for this specific bound. Recent work shows an $\tilde{O}(n^{0.4})$-approximation algorithm exists (Rubinstein & Song, 2022), which is consistent with an $n^{0.25}$ lower bound, but the specific hardness result should be cited.

Verdict: Warn — core claims correct, but the Wagner & Fischer attribution is imprecise and the approximation hardness bound needs a citation.

Well-written

Sections present: Motivation ✓, Name ✓, Reference ✓, Definition ✓, Variables ✓, Schema ✓, Problem Size ✓, Complexity ✓, How to solve ✓, Example Instance ✓.

Definition: Clear and precise — input (alphabet Σ, k strings), subsequence definition, objective (maximize length). ✓

Symbol consistency: $k$, $s_i$, $\Sigma$, $m$, $w$ all defined and consistent across sections. ✓

Example quality: 3 strings of length 6, non-trivial 3-string instance, optimal LCS = BCAB verified with explicit position traces. Pairwise LCS analysis adds insight. Excellent. ✓

Issues found:

1. Variables encoding: The Variables section defines $m$ variables (one per character of output $w$) with domain $\Sigma$. This doesn't map well to the Problem trait's dims() API because the number of variables (solution length) is unknown in advance. A more natural encoding for implementation would be binary variables over positions of the shortest string (include/exclude each position), giving dims() = [2; m]. This will need to be resolved during implementation.

2. Missing specific complexity bound: The Complexity section says "NP-hard (Maier, 1978)" for $k$ strings but doesn't provide the best-known exact algorithm's time bound (e.g., $O(2^m \cdot k \cdot n)$ for brute-force, or a better bound). The declare_variants! macro requires a concrete complexity string like "2^num_variables". This should be specified.

3. Missing Variants subsection: The Schema section doesn't discuss type parameters or variants. Since LCS has no graph/weight type params, this is fine — but explicitly stating "no variants" would be clearer.

Verdict: Warn — complete and well-structured but the variable encoding and complexity bound need refinement for implementation.

Recommendations

• Replace Wagner & Fischer citation with a more direct reference for the O(mn) LCS DP (e.g., "standard DP" or cite Hirschberg 1975 for the canonical presentation)
• Add a citation for the $n^{1/4-\varepsilon}$ inapproximability bound
• Add a concrete complexity string for declare_variants! (e.g., "2^total_length" or a tighter bound)
• Clarify the variable encoding — binary variables over positions of the shortest string would align better with the Problem trait