[Rule] Vertex Cover to Longest Common Subsequence

[isPANN]

Source: MinimumVertexCover
Target: LongestCommonSubsequence
Motivation: Establishes NP-completeness of LONGEST COMMON SUBSEQUENCE (for an arbitrary number of strings) via polynomial-time reduction from VERTEX COVER. While LCS for two strings is solvable in O(n²) time by dynamic programming, Maier (1978) showed the problem becomes NP-complete for an unbounded number of strings. The reduction uses a vertex-alphabet encoding: each vertex becomes a symbol, each edge yields a constraint string that forbids both endpoints from appearing together in any common subsequence.
Reference: Maier, D. (1978). "The complexity of some problems on subsequences and supersequences." Journal of the ACM 25(2), pp. 322–336. Also catalogued as SR10 in Garey & Johnson, Computers and Intractability, p. 228.

GJ Source Entry

[SR10] LONGEST COMMON SUBSEQUENCE
INSTANCE: Finite alphabet Σ, finite set R of strings from Σ*, and a positive integer K.
QUESTION: Is there a string w ∈ Σ* with |w| ≥ K such that w is a subsequence of each x ∈ R?
Reference: [Maier, 1978]. Transformation from VERTEX COVER.
Comment: Remains NP-complete even if |Σ| = 2. Solvable in polynomial time for any fixed K or for fixed |R| (by dynamic programming).

Reduction Algorithm

Given a MinimumVertexCover instance G = (V, E) with V = {0, 1, ..., n−1} and E = {e₁, ..., eₘ}, construct a LongestCommonSubsequence instance as follows:

1. Alphabet: Σ = {0, 1, ..., n−1}, one symbol per vertex. So alphabet_size = n.

2. Template string: S₀ = (0, 1, 2, ..., n−1), listing all vertices in sorted order. Length = n.

3. Edge strings: For each edge eⱼ = {u, v}, construct:
   Sⱼ = (0, ..., n−1 with u removed) ++ (0, ..., n−1 with v removed)
   Each half is in sorted order. Length = 2(n−1).

4. String set: R = {S₀, S₁, ..., Sₘ}, giving m + 1 strings total.

5. LCS bound: K' = n − K, where K is the vertex cover size. The LCS length equals the maximum independent set size.

Correctness (forward): Let I ⊆ V be an independent set of size n − K. The sorted sequence of symbols in I is a common subsequence of all strings:

• It is trivially a subsequence of S₀ since S₀ lists all vertices in order.
• For each edge string Sⱼ corresponding to edge {u, v}: since I is independent, at most one of u, v is in I. The symbol not in the edge endpoint set appears in both halves of Sⱼ. The symbol of the one endpoint that might be in I appears in the half where the other endpoint was removed. Therefore the sorted symbols of I appear as a subsequence.

Correctness (backward): Let w be a common subsequence of length ≥ n − K. Since w is a subsequence of S₀ = (0, 1, ..., n−1) and S₀ has no repeated symbols, w consists of distinct vertex symbols. For any edge {u, v}, the edge string Sⱼ = (V{u})(V{v}) contains u only in the second half and v only in the first half. If both u and v appeared in w, then since w must be a subsequence of Sⱼ, v must be matched before u — but w is also a subsequence of S₀ where u < v or v < u in some fixed order. This forces a contradiction for at least one ordering. Therefore at most one endpoint of each edge appears in w, so the symbols of w form an independent set. The complement V \ w is a vertex cover of size ≤ K.

Solution extraction: Given the LCS witness (a subsequence of symbols), the symbols present form an independent set. The vertex cover is the complement: config[v] = 1 if v does NOT appear in the LCS, config[v] = 0 if v appears in the LCS.

Time complexity of reduction: O(n · m) to construct all strings.

Size Overhead

Symbols:

• n = num_vertices of source MinimumVertexCover instance
• m = num_edges of source MinimumVertexCover instance

Target field	Expression	Derivation
alphabet_size	num_vertices	One symbol per vertex
num_strings	num_edges + 1	One template + one per edge
max_length	num_vertices	min string length = n (template S₀ has length n ≤ 2(n−1) for n ≥ 2)
total_length	num_vertices + num_edges * 2 * (num_vertices - 1)	S₀ has length n; each edge string has length 2(n−1)

Example

Source instance (MinimumVertexCover on path P₄):

• Vertices: V = {0, 1, 2, 3}, n = 4
• Edges: {0,1}, {1,2}, {2,3}, m = 3
• Minimum vertex cover: {1, 2} of size K = 2 (covers all edges)
• Maximum independent set: {0, 3} of size n − K = 2

Constructed target instance (LongestCommonSubsequence):

• Alphabet: Σ = {0, 1, 2, 3}, alphabet_size = 4
• Template string: S₀ = (0, 1, 2, 3), length 4
• Edge strings:
  • S₁ for edge {0, 1}: (1, 2, 3) ++ (0, 2, 3) = (1, 2, 3, 0, 2, 3), length 6
  • S₂ for edge {1, 2}: (0, 2, 3) ++ (0, 1, 3) = (0, 2, 3, 0, 1, 3), length 6
  • S₃ for edge {2, 3}: (0, 1, 3) ++ (0, 1, 2) = (0, 1, 3, 0, 1, 2), length 6
• String set: R = {S₀, S₁, S₂, S₃}, num_strings = 4
• max_length = min(4, 6, 6, 6) = 4
• LCS bound: K' = 4 − 2 = 2

Verification that (0, 3) is a common subsequence of length 2:

• S₀ = (0, 1, 2, 3): subsequence at positions 0, 3 ✓
• S₁ = (1, 2, 3, 0, 2, 3): match 0 at position 3, then 3 at position 5 ✓
• S₂ = (0, 2, 3, 0, 1, 3): match 0 at position 0, then 3 at position 5 ✓
• S₃ = (0, 1, 3, 0, 1, 2): match 0 at position 0, then 3 at position 2 ✓

Solution extraction:

• LCS witness = (0, 3) → independent set = {0, 3}
• Vertex cover = complement = {1, 2}
• Config: config = [0, 1, 1, 0] (v in cover ↔ config[v] = 1)
• Check: edge {0,1} covered by v1 ✓, edge {1,2} covered by v1 and v2 ✓, edge {2,3} covered by v2 ✓

Validation Method

• Closed-loop test: reduce a MinimumVertexCover instance to LongestCommonSubsequence, solve the target with BruteForce, extract solution, verify it is a valid vertex cover on the source
• Test with path P₄ as above (MVC = 2, LCS = 2)
• Test with triangle K₃ (MVC = 2, LCS = 1, independent set = any single vertex)
• Test with empty graph (no edges): MVC = 0, LCS = n (all vertices form the independent set)
• Verify that every constructed string only uses symbols in {0, ..., n−1}

References

• [Maier, 1978] David Maier. "The complexity of some problems on subsequences and supersequences." Journal of the ACM 25(2), pp. 322–336, 1978.
• [Garey & Johnson, 1979] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Problem SR10, p. 228.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MinimumVertexCover to LongestCommonSubsequence
Non-trivial	✅ Pass	Genuine structural transformation with string construction gadgets
Correctness	⚠️ Warn	Core reference (Maier 1978) is valid and in project bibliography; however the detailed binary-alphabet construction presented cannot be independently verified against the original paper and the issue's own worked example reveals self-contradictions
Well-written	❌ Fail	Multiple issues: incorrect overhead field names, broken worked example, inconsistent notation

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

No reduction path currently exists from MinimumVertexCover to LongestCommonSubsequence in the reduction graph (pred path returns no result). This is a novel reduction that would connect a core graph problem to a string problem, adding genuine value to the reduction graph.

The motivation is adequate — it explains the relationship between LCS for multiple strings and vertex cover, and notes that LCS for two strings is polynomial while the multi-string version is NP-complete.

Non-trivial

The reduction involves genuine structural transformation: encoding graph vertices and edges as binary strings with specific block structures, and relating vertex cover size to common subsequence length via a complementary counting argument. This is not a trivial relabeling or subtype coercion.

Correctness

References verified:

• Maier 1978 — "The Complexity of Some Problems on Subsequences and Supersequences", JACM 25(2), pp. 322-336. This paper exists in the project bibliography (references.bib) with matching title, author, journal, and year. Garey & Johnson entry SR10 confirms: "Transformation from VERTEX COVER" with NP-completeness even for |Σ| = 2. The core claim is correct.
• Wagner and Fischer 1974 — Also in the project bibliography. Cited for the polynomial-time two-string case. Valid.
• Bulteau et al. 2012 — Cited for bounded run-lengths hardness. Valid reference (found on Springer).

Concern: The detailed binary-alphabet construction in the issue (Steps 1-7) appears to be an AI-generated reconstruction rather than a faithful reproduction of Maier's original proof. The issue's own worked example (the 6-cycle C_6) reveals that the author could not successfully verify the construction — the "Corrected solution mapping" section contains contradictions and the author explicitly writes: "Wait, we must re-examine" and "The precise embedding uses the 0^n blocks as anchors... The full formal proof requires careful analysis." This suggests the detailed construction has not been verified against the original paper and may contain errors.

The simpler, well-known construction (using one symbol per vertex) described in other sources produces strings of length O(n) rather than O(n^2), which is a different reduction than what is presented here. The issue conflates two different approaches without clarity on which one should be implemented.

Well-written

4a — Information Completeness:

• Source: "Vertex Cover" — should specify MinimumVertexCover to match the codebase model name.
• Target: "Longest Common Subsequence" — matches LongestCommonSubsequence.
• Motivation: Present and substantive. ✓
• Reference: Present with three citations. ✓
• Reduction Algorithm: Present but see 4b below.
• Size Overhead: Present but has incorrect field names (see 4c).
• Validation Method: Present. ✓
• Example: Present but broken (see 4d).

4b — Algorithm Completeness:
The algorithm provides numbered steps, but the construction has not been successfully verified even by the issue author. The example section devolves into confusion and hand-waving ("The full formal proof requires careful analysis of the subsequence matching phase by phase"). An implementable reduction algorithm must be verifiable on a concrete example; this one is not.

4c — Symbol and Notation Consistency:

• The overhead table uses max_string_length but the actual LCS model size field is max_length (per pred show LongestCommonSubsequence --json).
• The overhead table uses bound_K which is not a size field on the LCS model. The actual LCS model stores the bound implicitly via max_length.
• The overhead expression num_vertices^2 + num_vertices - cover_bound references cover_bound, which is not a getter method on MinimumVertexCover. The source model is an optimization problem (minimize vertex cover), not a decision problem with an explicit bound parameter.
• Available LCS size fields: alphabet_size, max_length, num_strings, num_transitions, sum_triangular_lengths, total_length.
• Available MVC size fields: num_vertices, num_edges.

4d — Example Quality:
The example is broken. The author starts with a 6-cycle (good choice for non-trivial instance), but when attempting to verify the construction:

1. They construct the common subsequence T for independent set {v_1, v_3, v_5}.
2. They discover T is NOT a subsequence of S_1 (edge {v_1,v_2}) because S_1 lacks the 1-bit at position 1 which T requires.
3. The "Corrected solution mapping" attempts to explain this away but introduces further contradictions.
4. The example concludes with a hand-wave: "The precise embedding uses the 0^n blocks as anchors... The full formal proof requires careful analysis."

A worked example must be fully verified, not abandoned mid-way with a note that it "requires careful analysis."

Recommendations

• Obtain the actual Maier 1978 construction. The binary-alphabet construction in the issue appears to be an AI-generated reconstruction rather than a faithful reproduction of Maier's reduction. The original paper (DOI: 10.1145/322063.322075) should be consulted for the precise construction.
• Consider the vertex-alphabet construction instead. The simpler reduction (one symbol per vertex, template T = all vertices, edge strings with endpoints removed) is well-documented and easier to verify. However, it uses alphabet size = |V|, not binary. If binary alphabet is required, the original Maier construction must be faithfully reproduced.
• Fix the source problem name to MinimumVertexCover and address the decision-vs-optimization mismatch. The codebase model is an optimization problem; the reduction as stated assumes a decision version with an explicit bound K.
• Fix overhead field names to match actual model getters (max_length not max_string_length; remove bound_K; use total_length and num_strings).
• Provide a complete, verified worked example that traces through every step without gaps or contradictions.

[zazabap]

Issue Quality Check — Rule

Re-check after issue rewrite (previous check from 2026-03-29 found 1 fail, 1 warning).

Check	Result	Details
Usefulness	✅ Pass	No existing path from MinimumVertexCover to LongestCommonSubsequence
Non-trivial	✅ Pass	Genuine structural transformation: edge-string gadgets enforce independent set constraint
Correctness	✅ Pass	Maier 1978 verified in project bibliography; vertex-alphabet construction is standard and well-documented
Well-written	✅ Pass	All sections complete, overhead fields match model getters, worked P₄ example fully verified

Overall: 4 passed, 0 failed, 0 warnings

Previously: 2 passed, 1 warning, 1 failed → Now: 4 passed after issue rewrite with correct vertex-alphabet construction.

---

Usefulness

No reduction path currently exists from MinimumVertexCover to LongestCommonSubsequence (pred path returns no result). This is a novel reduction connecting a core graph problem to a string problem, adding genuine value to the reduction graph.

The motivation clearly explains the NP-completeness relationship and the role of Maier's 1978 result.

Non-trivial

The reduction constructs edge-specific constraint strings that force any common subsequence to represent an independent set. Each edge string Sⱼ = (V{u})(V{v}) is a non-trivial gadget that prevents both endpoints from appearing in any common subsequence. This is genuine structural transformation, not relabeling or coercion.

Correctness

References verified:

• Maier 1978 — present in project bibliography (references.bib) as maier1978. Title, author, journal (JACM 25(2)), year, and page range (322–336) all match. The paper establishes NP-completeness of LCS for unbounded number of strings via reduction from Vertex Cover.
• Garey & Johnson 1979 — SR10 entry confirms: "Transformation from VERTEX COVER."

The vertex-alphabet construction (one symbol per vertex, template + edge strings of length 2(n-1)) is the standard Maier construction. The correctness argument in the issue is sound:

• Forward direction: independent set symbols form a valid common subsequence because for each edge at most one endpoint is in the set.
• Backward direction: S₀ forces distinct symbols; edge strings force at most one endpoint per edge via the two-half structure.

The solution extraction (complement of LCS symbols = vertex cover) is correct.

Well-written

4a — Information Completeness: All required sections present and substantive: Source (MinimumVertexCover), Target (LongestCommonSubsequence), Motivation, Reference, Reduction Algorithm (5 numbered steps + correctness + extraction), Size Overhead (4-row table), Example (P₄), Validation Method (4 test cases), References.

4b — Algorithm Completeness: The algorithm is a complete step-by-step procedure: alphabet construction, template string, edge string construction (with explicit formula), string set assembly, and LCS bound. Solution extraction is clearly defined. All steps are implementable.

4c — Symbol and Notation Consistency:

• n and m defined as num_vertices and num_edges respectively.
• All overhead expressions use valid MVC source getters (num_vertices, num_edges).
• All target field names match actual LCS size fields: alphabet_size, num_strings, max_length, total_length.
• No undefined symbols or notation mismatches.

4d — Example Quality:

• Non-trivial: Path P₄ with 4 vertices and 3 edges — enough structure to exercise the reduction.
• Round-trip testable: Multiple suboptimal feasible covers exist (e.g., {0,1,2} size 3, {1,2,3} size 3, {0,1,2,3} size 4) in addition to the optimal {1,2} size 2.
• Fully worked: Shows source instance, all 4 constructed strings with explicit content, verifies (0,3) as a common subsequence of each string with position-level matching, and traces solution extraction back to the vertex cover config [0,1,1,0].
• No contradictions or gaps in the verification.

[GiggleLiu]

Implemented in PR #1010.