[Rule] LongestCommonSubsequence to MaximumIndependentSet

[zazabap]

Source: LongestCommonSubsequence
Target: MaximumIndependentSet
Motivation: Connects string problems to graph theory; enables solving LCS via MaxIS solvers and reveals structural equivalence between subsequence ordering and graph independence.
Reference: Apostolico & Guerra, 1987; Santini, Blum, Djukanovic et al., 2021

Reduction Algorithm

Notation:

• Source: $k$ strings $s_1, \ldots, s_k$ over alphabet $\Sigma$, with lengths $n_1, \ldots, n_k$
• Target: undirected graph $G = (V, E)$

Step 1 — Construct match nodes $V$:

A node $v = (p_1, p_2, \ldots, p_k)$ is created for each $k$-tuple of positions such that $s_1[p_1] = s_2[p_2] = \cdots = s_k[p_k]$ (all strings have the same character at their respective positions).

$$V = {(p_1, \ldots, p_k) : s_1[p_1] = s_2[p_2] = \cdots = s_k[p_k]}$$

Step 2 — Construct conflict edges $E$:

Two nodes $u = (a_1, \ldots, a_k)$ and $v = (b_1, \ldots, b_k)$ are connected by an edge if they conflict — i.e., they cannot both appear in a valid common subsequence. A conflict occurs when the position differences are not consistently ordered across all strings:

$${u, v} \in E \iff \text{NOT}\ (\forall i: a_i < b_i) \ \text{AND NOT}\ (\forall i: a_i > b_i)$$

In other words, there exist indices $i, j$ such that $a_i &lt; b_i$ but $a_j &gt; b_j$ (a "crossing"), or $a_i = b_i$ for some $i$ (same position used twice).

Variable mapping: Each LCS character corresponds to a selected node; each MaxIS vertex in the independent set corresponds to a matched position tuple.

Objective: $\text{MaxIS}(G) = \text{LCS}(s_1, \ldots, s_k)$. An independent set of size $L$ gives a common subsequence of length $L$, and vice versa.

Required Model Extension

The implementer must add the following getter to LongestCommonSubsequence in src/models/misc/longest_common_subsequence.rs in the same PR as the reduction rule:

/// Returns the cross-frequency product: the sum over each alphabet symbol
/// of the product of that symbol's frequency across all input strings.
///
/// Formally: Σ_{c ∈ 0..alphabet_size} ∏_{i=1..k} count(c, strings[i])
/// where count(c, s) is the number of occurrences of symbol c in string s.
///
/// This equals the exact number of match-node vertices in the LCS → MaxIS
/// reduction graph.
pub fn cross_frequency_product(&self) -> usize {
    (0..self.alphabet_size)
        .map(|c| {
            self.strings
                .iter()
                .map(|s| s.iter().filter(|&&sym| sym == c).count())
                .product::<usize>()
        })
        .sum()
}

This getter is referenced in the #[reduction(overhead)] attribute as cross_frequency_product.

Size Overhead

Target metric (code name)	Expression
num_vertices	cross_frequency_product
num_edges	cross_frequency_product^2

Where cross_frequency_product = $\sum_{c \in \Sigma} \prod_{i=1}^{k} \text{count}(c, s_i)$. This equals the exact number of match nodes $|V|$. The edge count is a worst-case bound (all node pairs conflict).

Validation Method

Closed-loop testing: solve LCS by brute-force (enumerate subsequences of shortest string), solve the reduced MaxIS instance, and verify that both give the same optimal value. Test on instances with varying alphabet sizes and string counts ($k = 2, 3, 4$).

Example

Source instance: $k = 2$, $s_1$ = ABAC, $s_2$ = BACA, alphabet $\Sigma = {A, B, C}$.

Step 1 — Match nodes:

Node	$s_1$ pos	$s_2$ pos	Character
$v_0$	0	1	A
$v_1$	0	3	A
$v_2$	1	0	B
$v_3$	2	1	A
$v_4$	2	3	A
$v_5$	3	2	C

Step 2 — Conflict edges (9 edges):

Edge	Reason
$v_0 - v_1$	same $s_1$ position (0)
$v_0 - v_2$	crossing: $s_1$: $0<1$, $s_2$: $1>0$
$v_0 - v_3$	same $s_2$ position (1)
$v_1 - v_2$	crossing: $s_1$: $0<1$, $s_2$: $3>0$
$v_1 - v_3$	crossing: $s_1$: $0<2$, $s_2$: $3>1$
$v_1 - v_4$	same $s_2$ position (3)
$v_1 - v_5$	crossing: $s_1$: $0<3$, $s_2$: $3>2$
$v_3 - v_4$	same $s_1$ position (2)
$v_4 - v_5$	crossing: $s_1$: $2<3$, $s_2$: $3>2$

MaxIS solution: ${v_2, v_3, v_5}$ (size 3, unique).

Node	Position	Char
$v_2$	$s_1[1], s_2[0]$	B
$v_3$	$s_1[2], s_2[1]$	A
$v_5$	$s_1[3], s_2[2]$	C

Extracted LCS: BAC (length 3). Verified: B-A-C is a subsequence of both ABAC (positions 1,2,3) and BACA (positions 0,1,2).

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Source (LCS) not yet in codebase; novel reduction
Non-trivial	✅ Pass	Match-node graph construction with conflict edges
Correctness	❌ Fail	Both DOIs are wrong — point to unrelated papers
Well-written	⚠️ Warn	Overhead uses inequality bounds rather than exact expressions

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

LongestCommonSubsequence does not exist in the codebase. This would connect string/sequence problems to the graph theory portion of the reduction graph. Requires implementing the LCS model first.

Non-trivial

Constructs a new graph from scratch: vertices are match-position tuples, edges encode crossing/shared-position conflicts. Transforms a sequence problem into a graph problem with fundamentally different input structure.

Correctness — FAIL

Both DOIs are wrong:

1. Apostolico & Guerra (1987): Issue cites DOI 10.1137/0216009, which resolves to "A Note on Bottom-Up Skew Heaps" (SIAM J. Computing) — an unrelated paper. The actual paper is "The Longest Common Subsequence Problem Revisited," published in Algorithmica (1987), vol. 2, pp. 315–336, DOI 10.1007/BF01840365. Furthermore, this paper focuses on algorithmic speedups for computing LCS, not the LCS-to-MIS reduction.

2. Baxter et al. (2004): Issue cites DOI 10.1007/978-3-540-27801-6_12, which resolves to "A Simple Optimal Representation for Balanced Parentheses" (CPM 2004) by Geary, Rahman, Raman & Raman — no paper by "Baxter et al." exists in CPM 2004 proceedings.

Better reference: The explicit LCS-to-clique/MIS transformation is described in Santini, Blum & Djukanovic (2021), "Solving Longest Common Subsequence Problems via a Transformation to the Maximum Clique Problem," Computers & Operations Research, vol. 125, 105089.

Note: The reduction algorithm itself is mathematically correct — I independently verified the example (6 nodes, 9 edges, unique MIS {v2,v3,v5} of size 3 yielding LCS="BAC").

Well-written — WARN

All sections present. Algorithm is clear and implementable. Example is well-worked and correct.

Issue: Overhead table uses inequality bounds (≤) rather than exact expressions. The #[reduction(overhead)] macro requires exact expressions in terms of source getter methods, not inequalities. The actual vertex count depends on character frequencies, not just string lengths.

Required fixes

1. Fix Apostolico & Guerra DOI to 10.1007/BF01840365 (or replace with a more relevant reference)
2. Replace "Baxter et al. 2004" entirely — paper does not exist at cited DOI. Consider Santini et al. 2021
3. Rewrite overhead as exact expressions using source getter methods