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(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
29
30        Ok({
31            let mut cover = vec![true; self.num_vertices];
32            for &symbol in target_solution {
33                let Some(symbol) = symbol else { break };
34                cover[symbol] = false;
35            }
36            cover
37        })
38    }
39}
40
41#[reduction(
42    transform = {
43        exact {
44            alphabet_size = "num_vertices",
45            num_strings = "num_edges + 1",
46            max_length = "num_vertices",
47            total_length = "num_vertices + 2 * num_edges * num_vertices - 2 * num_edges",
48            sum_triangular_lengths = "num_vertices * (num_vertices + 1) / 2 + num_edges * (2 * num_vertices - 2) * (2 * num_vertices - 1) / 2",
49        },
50        upper_bound {
51            num_transitions = "num_vertices",
52        },
53    },
54    unavailable = {
55        cross_frequency_product = "each symbol occurs once in the base string and at most twice in each of num_edges edge strings; the source-only bound num_vertices * 2^num_edges needs a variable exponent, unsupported by the exact evaluator; endpoint incidences determine the exact product",
56    }
57)]
58impl ReduceTo<LongestCommonSubsequence> for MinimumVertexCover<SimpleGraph, One> {
59    type Result = ReductionVCToLCS;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let num_vertices = self.graph().num_vertices();
63        let mut strings = Vec::with_capacity(self.graph().num_edges() + 1);
64        strings.push((0..num_vertices).collect());
65
66        for (left, right) in self.graph().edges() {
67            // The backward direction relies on each edge string forcing the
68            // larger endpoint to appear before the smaller one.
69            let (u, v) = if left < right {
70                (left, right)
71            } else {
72                (right, left)
73            };
74            let mut edge_string = string_without_vertex(num_vertices, u);
75            edge_string.extend(string_without_vertex(num_vertices, v));
76            strings.push(edge_string);
77        }
78
79        let target = LongestCommonSubsequence::new(num_vertices, strings);
80        Ok(ReductionVCToLCS {
81            target,
82            num_vertices,
83        })
84    }
85}
86
87fn string_without_vertex(num_vertices: usize, omitted: usize) -> Vec<usize> {
88    (0..num_vertices)
89        .filter(|&vertex| vertex != omitted)
90        .collect()
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    use crate::export::SolutionPair;
96
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "minimumvertexcover_to_longestcommonsubsequence",
99        build: || {
100            let source = MinimumVertexCover::new(
101                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
102                vec![One; 4],
103            );
104            crate::example_db::specs::rule_example_with_witness::<_, LongestCommonSubsequence>(
105                source,
106                SolutionPair {
107                    source_config: serde_json::json!(vec![false, true, true, false]),
108                    target_config: serde_json::json!(vec![Some(0), Some(3), None, None]),
109                },
110            )
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/minimumvertexcover_longestcommonsubsequence.rs"]
117mod tests;
problemreductions/rules/minimumvertexcover_longestcommonsubsequence.rs

problemreductions/rules/
minimumvertexcover_longestcommonsubsequence.rs
