problemreductions/rules/
longestcommonsubsequence_maximumindependentset.rs

1//! Reduction from LongestCommonSubsequence to MaximumIndependentSet.
2//!
3//! Constructs a conflict graph where vertices are match-node k-tuples
4//! (positions in each string that share the same character) and edges
5//! connect conflicting tuples that cannot both appear in a valid common
6//! subsequence. A maximum independent set in this graph corresponds to
7//! a longest common subsequence.
8//!
9//! Reference: Santini, Blum, Djukanovic et al. (2021),
10//! "Solving Longest Common Subsequence Problems via a Transformation
11//! to the Maximum Clique Problem," Computers & Operations Research.
12
13use crate::models::graph::MaximumIndependentSet;
14use crate::models::misc::LongestCommonSubsequence;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17use crate::topology::SimpleGraph;
18use crate::types::One;
19
20/// Result of reducing LongestCommonSubsequence to MaximumIndependentSet.
21///
22/// Each vertex in the target graph corresponds to a match-node k-tuple
23/// `(p_1, ..., p_k)` where all strings have the same character at their
24/// respective positions.
25#[derive(Debug, Clone)]
26pub struct ReductionLCSToIS {
27    /// The target MaximumIndependentSet problem.
28    target: MaximumIndependentSet<SimpleGraph, One>,
29    /// Match-node k-tuples: `match_nodes[v]` gives the position tuple for vertex v.
30    match_nodes: Vec<Vec<usize>>,
31    /// Character for each match node.
32    match_chars: Vec<usize>,
33    /// Maximum possible subsequence length in the source problem.
34    max_length: usize,
35}
36
37impl ReductionResult for ReductionLCSToIS {
38    type Source = LongestCommonSubsequence;
39    type Target = MaximumIndependentSet<SimpleGraph, One>;
40
41    fn target_problem(&self) -> &Self::Target {
42        &self.target
43    }
44
45    /// Extract an LCS solution from a MaximumIndependentSet solution.
46    ///
47    /// Selected vertices correspond to match nodes. Sort by position in
48    /// the first string to get the subsequence order, then pad to `max_length`.
49    fn extract_solution(
50        &self,
51        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
52    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
53        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
54
55        Ok({
56            // Collect selected match nodes with their characters
57            let mut selected: Vec<(usize, usize)> = target_solution
58                .iter()
59                .enumerate()
60                .filter(|(_, &v)| v)
61                .map(|(i, _)| (self.match_nodes[i][0], self.match_chars[i]))
62                .collect();
63            // Sort by position in the first string
64            selected.sort_by_key(|&(pos, _)| pos);
65
66            // Build config: characters followed by padding
67            let mut config = Vec::with_capacity(self.max_length);
68            for &(_, ch) in &selected {
69                config.push(Some(ch));
70            }
71            // Pad with alphabet_size (the padding symbol)
72            while config.len() < self.max_length {
73                config.push(None);
74            }
75            config
76        })
77    }
78}
79
80#[reduction(
81    transform = upper_bound {
82        num_vertices = "cross_frequency_product",
83        num_edges = "cross_frequency_product^2",
84    }
85)]
86impl ReduceTo<MaximumIndependentSet<SimpleGraph, One>> for LongestCommonSubsequence {
87    type Result = ReductionLCSToIS;
88
89    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
90        let strings = self.strings();
91        let k = self.num_strings();
92
93        // Step 1: Build match nodes.
94        // For each character c, find all k-tuples of positions where every
95        // string has character c at its respective position.
96        let mut match_nodes: Vec<Vec<usize>> = Vec::new();
97        let mut match_chars: Vec<usize> = Vec::new();
98
99        for c in 0..self.alphabet_size() {
100            // For each string, collect positions where character c appears
101            let positions_per_string: Vec<Vec<usize>> = strings
102                .iter()
103                .map(|s| {
104                    s.iter()
105                        .enumerate()
106                        .filter(|(_, &sym)| sym == c)
107                        .map(|(i, _)| i)
108                        .collect()
109                })
110                .collect();
111
112            // Generate all k-tuples (Cartesian product of position lists)
113            let tuples = cartesian_product(&positions_per_string);
114            for tuple in tuples {
115                match_nodes.push(tuple);
116                match_chars.push(c);
117            }
118        }
119
120        let num_vertices = match_nodes.len();
121
122        // Step 2: Build conflict edges.
123        // Two nodes u = (a_1, ..., a_k) and v = (b_1, ..., b_k) conflict when
124        // they cannot both appear in a valid common subsequence: NOT(all a_i < b_i)
125        // AND NOT(all a_i > b_i).
126        let mut edges: Vec<(usize, usize)> = Vec::new();
127
128        for i in 0..num_vertices {
129            for j in (i + 1)..num_vertices {
130                if nodes_conflict(&match_nodes[i], &match_nodes[j], k) {
131                    edges.push((i, j));
132                }
133            }
134        }
135
136        let target = MaximumIndependentSet::new(
137            SimpleGraph::new(num_vertices, edges),
138            vec![One; num_vertices],
139        );
140
141        Ok(ReductionLCSToIS {
142            target,
143            match_nodes,
144            match_chars,
145            max_length: self.max_length(),
146        })
147    }
148}
149
150/// Check whether two match nodes conflict (cannot both be in a common subsequence).
151///
152/// Two nodes `u = (a_1, ..., a_k)` and `v = (b_1, ..., b_k)` conflict when
153/// NOT (all a_i < b_i) AND NOT (all a_i > b_i).
154fn nodes_conflict(u: &[usize], v: &[usize], k: usize) -> bool {
155    let mut all_less = true;
156    let mut all_greater = true;
157    for i in 0..k {
158        if u[i] >= v[i] {
159            all_less = false;
160        }
161        if u[i] <= v[i] {
162            all_greater = false;
163        }
164    }
165    !all_less && !all_greater
166}
167
168/// Compute the Cartesian product of a list of position vectors.
169fn cartesian_product(lists: &[Vec<usize>]) -> Vec<Vec<usize>> {
170    if lists.is_empty() {
171        return vec![vec![]];
172    }
173
174    let mut result = vec![vec![]];
175    for list in lists {
176        let mut new_result = Vec::new();
177        for prefix in &result {
178            for &item in list {
179                let mut new_tuple = prefix.clone();
180                new_tuple.push(item);
181                new_result.push(new_tuple);
182            }
183        }
184        result = new_result;
185    }
186    result
187}
188
189#[cfg(feature = "example-db")]
190pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
191    use crate::export::SolutionPair;
192
193    /// Build the example from the issue: k=2, s1="ABAC", s2="BACA", alphabet={A,B,C}.
194    fn lcs_abac_baca() -> LongestCommonSubsequence {
195        // A=0, B=1, C=2
196        LongestCommonSubsequence::new(
197            3,
198            vec![
199                vec![0, 1, 0, 2], // ABAC
200                vec![1, 0, 2, 0], // BACA
201            ],
202        )
203    }
204
205    vec![crate::example_db::specs::RuleExampleSpec {
206        id: "longestcommonsubsequence_to_maximumindependentset",
207        build: || {
208            // Issue example: MIS solution {v2, v4, v5} gives LCS "BAC" (length 3).
209            // Match nodes (ordered by character):
210            //   c=A(0): v0=(0,1), v1=(0,3), v2=(2,1), v3=(2,3)
211            //   c=B(1): v4=(1,0)
212            //   c=C(2): v5=(3,2)
213            // MIS {v2, v4, v5} => positions B@(1,0), A@(2,1), C@(3,2)
214            // source_config = [1, 0, 2, null] (B, A, C, padding)
215            crate::example_db::specs::rule_example_with_witness::<
216                _,
217                MaximumIndependentSet<SimpleGraph, One>,
218            >(
219                lcs_abac_baca(),
220                SolutionPair {
221                    source_config: serde_json::json!(vec![Some(1), Some(0), Some(2), None]),
222                    target_config: serde_json::json!(vec![false, false, true, false, true, true]),
223                },
224            )
225        },
226    }]
227}
228
229#[cfg(test)]
230#[path = "../unit_tests/rules/longestcommonsubsequence_maximumindependentset.rs"]
231mod tests;
problemreductions/rules/longestcommonsubsequence_maximumindependentset.rs

problemreductions/rules/
longestcommonsubsequence_maximumindependentset.rs
