problemreductions/rules/
minimumvertexcover_comparativecontainment.rs

1//! Reduction from Decision Minimum Vertex Cover to Comparative Containment.
2//!
3//! Implements the Plaisted (1976) construction (Garey & Johnson SP10): given a
4//! graph `G = (V, E)` and a bound `K`, build a Comparative Containment instance
5//! over universe `X = V` with two weighted set families `R` and `S` such that a
6//! subset `Y ⊆ X` satisfies the containment inequality iff `Y` is a vertex
7//! cover of `G` of size at most `K`.
8//!
9//! - For each vertex `v`, add `R_v = V \ {v}` with weight `1`. The total
10//!   R-weight equals `n - |Y|`.
11//! - For each edge `e = {u, v}`, add `S_e = V \ {u, v}` with weight `n + 1`.
12//!   Each uncovered edge contributes a penalty larger than the maximum possible
13//!   R-weight, so any feasible `Y` must cover every edge.
14//! - One budget set `S_0 = V` with weight `n - K`. The containment inequality
15//!   becomes `K - |Y| ≥ (n + 1) · (# uncovered edges)`.
16//!
17//! Source: `Decision<MinimumVertexCover<SimpleGraph, i32>>` with unit weights.
18//! See `decisionminimumvertexcover_hamiltoniancircuit.rs` for the analogous
19//! unit-weight assertion pattern.
20
21use crate::models::decision::Decision;
22use crate::models::graph::MinimumVertexCover;
23use crate::models::set::ComparativeContainment;
24use crate::reduction;
25use crate::rules::traits::{ReduceTo, ReductionResult};
26use crate::topology::{Graph, SimpleGraph};
27
28/// Result of reducing `Decision<MinimumVertexCover<SimpleGraph, i32>>` to
29/// `ComparativeContainment<i32>`.
30#[derive(Debug, Clone)]
31pub struct ReductionDecisionMVCToComparativeContainment {
32    target: ComparativeContainment<i32>,
33    num_source_vertices: usize,
34    /// If `Some`, the bound makes every vertex subset trivially feasible
35    /// (`K ≥ n`); the reduction emits an empty target instance and any
36    /// extracted source configuration is forced to be a YES instance.
37    trivial_yes: Option<Vec<usize>>,
38}
39
40impl ReductionResult for ReductionDecisionMVCToComparativeContainment {
41    type Source = Decision<MinimumVertexCover<SimpleGraph, i32>>;
42    type Target = ComparativeContainment<i32>;
43
44    fn target_problem(&self) -> &Self::Target {
45        &self.target
46    }
47
48    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
49        if let Some(witness) = &self.trivial_yes {
50            return witness.clone();
51        }
52        let mut cover = vec![0; self.num_source_vertices];
53        for (vertex, &selected) in target_solution
54            .iter()
55            .take(self.num_source_vertices)
56            .enumerate()
57        {
58            cover[vertex] = selected;
59        }
60        cover
61    }
62}
63
64#[reduction(
65    overhead = {
66        universe_size = "num_vertices",
67        num_r_sets = "num_vertices",
68        num_s_sets = "num_edges + 1",
69    }
70)]
71impl ReduceTo<ComparativeContainment<i32>> for Decision<MinimumVertexCover<SimpleGraph, i32>> {
72    type Result = ReductionDecisionMVCToComparativeContainment;
73
74    fn reduce_to(&self) -> Self::Result {
75        let weights = self.inner().weights();
76        assert!(
77            weights.iter().all(|&weight| weight == 1),
78            "Plaisted 1976 reduction requires unit vertex weights"
79        );
80
81        let num_vertices = self.inner().graph().num_vertices();
82        let raw_bound = *self.bound();
83
84        // Trivially NO corner case: a negative bound cannot be met by any
85        // (nonnegative) cover size. Emit an unsatisfiable target: universe of
86        // size 1 with a single S-set {0} and no R-sets, so the R-weight is
87        // always 0 < 1 = S-weight regardless of Y.
88        if raw_bound < 0 {
89            let target = ComparativeContainment::with_weights(
90                1,
91                Vec::new(),
92                vec![vec![0]],
93                Vec::<i32>::new(),
94                vec![1i32],
95            );
96            return ReductionDecisionMVCToComparativeContainment {
97                target,
98                num_source_vertices: num_vertices,
99                trivial_yes: None,
100            };
101        }
102
103        // Trivial YES corner case: when K >= n, every vertex subset of size at
104        // most n is a feasible cover (in particular the all-ones configuration
105        // covers every edge), so the answer is YES regardless of the graph.
106        // Emit an empty target instance (universe size 0, no R/S sets); its
107        // unique configuration is trivially satisfying.
108        if raw_bound >= num_vertices as i32 {
109            let target = ComparativeContainment::with_weights(
110                0,
111                Vec::new(),
112                Vec::new(),
113                Vec::<i32>::new(),
114                Vec::<i32>::new(),
115            );
116            // The all-ones configuration is always a vertex cover with size
117            // n <= K.
118            let witness = vec![1; num_vertices];
119            return ReductionDecisionMVCToComparativeContainment {
120                target,
121                num_source_vertices: num_vertices,
122                trivial_yes: Some(witness),
123            };
124        }
125
126        let k = self.k();
127        let edges = self.inner().graph().edges();
128        let n = num_vertices;
129
130        // R sets: R_v = V \ {v} for each vertex v, weight 1.
131        let r_sets: Vec<Vec<usize>> = (0..n).map(|v| complement_singleton(n, v)).collect();
132        let r_weights: Vec<i32> = vec![1; n];
133
134        // S sets: one per edge plus a single budget set.
135        let mut s_sets: Vec<Vec<usize>> = Vec::with_capacity(edges.len() + 1);
136        let mut s_weights: Vec<i32> = Vec::with_capacity(edges.len() + 1);
137
138        let edge_weight =
139            i32::try_from(n + 1).expect("Plaisted edge-penalty weight (n + 1) must fit in i32");
140        for &(u, v) in &edges {
141            s_sets.push(complement_pair(n, u, v));
142            s_weights.push(edge_weight);
143        }
144        // Budget set S_0 = V with weight n - K. Since 0 <= K < n here, this is
145        // a positive integer.
146        let budget_weight =
147            i32::try_from(n - k).expect("Plaisted budget weight (n - K) must fit in i32");
148        s_sets.push((0..n).collect());
149        s_weights.push(budget_weight);
150
151        let target = ComparativeContainment::with_weights(n, r_sets, s_sets, r_weights, s_weights);
152
153        ReductionDecisionMVCToComparativeContainment {
154            target,
155            num_source_vertices: n,
156            trivial_yes: None,
157        }
158    }
159}
160
161fn complement_singleton(n: usize, v: usize) -> Vec<usize> {
162    (0..n).filter(|&x| x != v).collect()
163}
164
165fn complement_pair(n: usize, u: usize, v: usize) -> Vec<usize> {
166    (0..n).filter(|&x| x != u && x != v).collect()
167}
168
169#[cfg(feature = "example-db")]
170pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
171    use crate::export::SolutionPair;
172
173    vec![crate::example_db::specs::RuleExampleSpec {
174        id: "decisionminimumvertexcover_to_comparativecontainment",
175        build: || {
176            // Path P_4: 0-1-2-3, bound K=2. Minimum cover {1,2} has size 2.
177            let inner = MinimumVertexCover::new(
178                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
179                vec![1i32; 4],
180            );
181            let source = Decision::new(inner, 2);
182            crate::example_db::specs::rule_example_with_witness::<_, ComparativeContainment<i32>>(
183                source,
184                SolutionPair {
185                    source_config: vec![0, 1, 1, 0],
186                    target_config: vec![0, 1, 1, 0],
187                },
188            )
189        },
190    }]
191}
192
193#[cfg(test)]
194#[path = "../unit_tests/rules/minimumvertexcover_comparativecontainment.rs"]
195mod tests;
problemreductions/rules/minimumvertexcover_comparativecontainment.rs

problemreductions/rules/
minimumvertexcover_comparativecontainment.rs
