problemreductions/rules/
minimumvertexcover_longestcommonsubsequence.rs

1//! Reduction from MinimumVertexCover (unit-weight) to LongestCommonSubsequence.
2
3use crate::models::graph::MinimumVertexCover;
4use crate::models::misc::LongestCommonSubsequence;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::topology::{Graph, SimpleGraph};
8use crate::types::One;
9
10#[derive(Debug, Clone)]
11pub struct ReductionVCToLCS {
12    target: LongestCommonSubsequence,
13    num_vertices: usize,
14}
15
16impl ReductionResult for ReductionVCToLCS {
17    type Source = MinimumVertexCover<SimpleGraph, One>;
18    type Target = LongestCommonSubsequence;
19
20    fn target_problem(&self) -> &Self::Target {
21        &self.target
22    }
23
24    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
25        let mut cover = vec![1; self.num_vertices];
26        for &symbol in target_solution {
27            if symbol >= self.num_vertices {
28                break;
29            }
30            cover[symbol] = 0;
31        }
32        cover
33    }
34}
35
36#[reduction(
37    overhead = {
38        alphabet_size = "num_vertices",
39        num_strings = "num_edges + 1",
40        max_length = "num_vertices",
41        total_length = "num_vertices + 2 * num_edges * num_vertices - 2 * num_edges",
42    }
43)]
44impl ReduceTo<LongestCommonSubsequence> for MinimumVertexCover<SimpleGraph, One> {
45    type Result = ReductionVCToLCS;
46
47    fn reduce_to(&self) -> Self::Result {
48        let num_vertices = self.graph().num_vertices();
49        let mut strings = Vec::with_capacity(self.graph().num_edges() + 1);
50        strings.push((0..num_vertices).collect());
51
52        for (left, right) in self.graph().edges() {
53            // The backward direction relies on each edge string forcing the
54            // larger endpoint to appear before the smaller one.
55            let (u, v) = if left < right {
56                (left, right)
57            } else {
58                (right, left)
59            };
60            let mut edge_string = string_without_vertex(num_vertices, u);
61            edge_string.extend(string_without_vertex(num_vertices, v));
62            strings.push(edge_string);
63        }
64
65        let target = LongestCommonSubsequence::new(num_vertices, strings);
66        ReductionVCToLCS {
67            target,
68            num_vertices,
69        }
70    }
71}
72
73fn string_without_vertex(num_vertices: usize, omitted: usize) -> Vec<usize> {
74    (0..num_vertices)
75        .filter(|&vertex| vertex != omitted)
76        .collect()
77}
78
79#[cfg(feature = "example-db")]
80pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
81    use crate::export::SolutionPair;
82
83    vec![crate::example_db::specs::RuleExampleSpec {
84        id: "minimumvertexcover_to_longestcommonsubsequence",
85        build: || {
86            let source = MinimumVertexCover::new(
87                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
88                vec![One; 4],
89            );
90            crate::example_db::specs::rule_example_with_witness::<_, LongestCommonSubsequence>(
91                source,
92                SolutionPair {
93                    source_config: vec![0, 1, 1, 0],
94                    target_config: vec![0, 3, 4, 4],
95                },
96            )
97        },
98    }]
99}
100
101#[cfg(test)]
102#[path = "../unit_tests/rules/minimumvertexcover_longestcommonsubsequence.rs"]
103mod tests;
problemreductions/rules/minimumvertexcover_longestcommonsubsequence.rs

problemreductions/rules/
minimumvertexcover_longestcommonsubsequence.rs
