problemreductions/rules/
minimumvertexcover_ensemblecomputation.rs

1//! Reduction from MinimumVertexCover (unit-weight) to EnsembleComputation.
2//!
3//! Given a graph G = (V, E), construct an EnsembleComputation instance where:
4//! - Universe A = V ∪ {a₀} (fresh element a₀ at index |V|)
5//! - Collection C = {{a₀, u, v} : {u,v} ∈ E}
6//! - Budget = |V| + |E| (search space bound; the optimal value encodes K*)
7//!
8//! The minimum sequence length is K* + |E|, where K* is the minimum vertex
9//! cover size. This follows from the Garey & Johnson proof (PO9): each cover
10//! vertex contributes one {a₀} ∪ {v} operation, and each edge contributes
11//! one {u} ∪ z_k operation.
12//!
13//! Reference: Garey & Johnson, *Computers and Intractability*, Appendix Problem PO9.
14
15use crate::models::graph::MinimumVertexCover;
16use crate::models::misc::EnsembleComputation;
17use crate::reduction;
18use crate::rules::traits::{ReduceTo, ReductionResult};
19use crate::topology::{Graph, SimpleGraph};
20use crate::types::One;
21
22/// Result of reducing MinimumVertexCover to EnsembleComputation.
23#[derive(Debug, Clone)]
24pub struct ReductionVCToEC {
25    target: EnsembleComputation,
26    /// Number of vertices in the source graph (= index of fresh element a₀).
27    num_vertices: usize,
28}
29
30impl ReductionResult for ReductionVCToEC {
31    type Source = MinimumVertexCover<SimpleGraph, One>;
32    type Target = EnsembleComputation;
33
34    fn target_problem(&self) -> &Self::Target {
35        &self.target
36    }
37
38    /// Extract a vertex cover from an EnsembleComputation witness.
39    ///
40    /// The GJ proof shows that any minimum-length sequence can be normalized
41    /// so that only two forms of operations appear:
42    /// - z_i = {a₀} ∪ {v}  — vertex v is in the cover
43    /// - z_j = {u} ∪ z_k   — edge {u, v_r} is covered by v_r
44    ///
45    /// We collect all vertices that appear as singleton operands (index < |V|)
46    /// in the meaningful steps only (before all required subsets are covered).
47    /// Padding steps beyond the coverage point are ignored.
48    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
49        use crate::traits::Problem;
50        use crate::types::Min;
51
52        let meaningful_steps = match self.target.evaluate(target_solution) {
53            Min(Some(n)) => n,
54            _ => return vec![0; self.num_vertices],
55        };
56        let mut cover = vec![0usize; self.num_vertices];
57
58        for step in 0..meaningful_steps {
59            let left = target_solution[2 * step];
60            let right = target_solution[2 * step + 1];
61
62            if left < self.num_vertices {
63                cover[left] = 1;
64            }
65            if right < self.num_vertices {
66                cover[right] = 1;
67            }
68        }
69
70        cover
71    }
72}
73
74#[reduction(
75    overhead = {
76        universe_size = "num_vertices + 1",
77        num_subsets = "num_edges",
78    }
79)]
80impl ReduceTo<EnsembleComputation> for MinimumVertexCover<SimpleGraph, One> {
81    type Result = ReductionVCToEC;
82
83    fn reduce_to(&self) -> Self::Result {
84        let num_vertices = self.graph().num_vertices();
85        let edges = self.graph().edges();
86        let num_edges = edges.len();
87        let a0 = num_vertices; // fresh element index
88
89        // Universe A = V ∪ {a₀}, size = |V| + 1
90        let universe_size = num_vertices + 1;
91
92        // Collection C: for each edge {u, v}, add subset {a₀, u, v}
93        let subsets: Vec<Vec<usize>> = edges.iter().map(|&(u, v)| vec![a0, u, v]).collect();
94
95        // Budget bounds the search space; the optimal sequence length
96        // is K* + |E| where K* is the minimum vertex cover size.
97        let budget = num_vertices + num_edges;
98
99        let target = EnsembleComputation::new(universe_size, subsets, budget);
100
101        ReductionVCToEC {
102            target,
103            num_vertices,
104        }
105    }
106}
107
108#[cfg(feature = "example-db")]
109pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
110    use crate::export::SolutionPair;
111
112    vec![crate::example_db::specs::RuleExampleSpec {
113        id: "minimumvertexcover_to_ensemblecomputation",
114        build: || {
115            // Single edge graph: 2 vertices {0,1}, 1 edge (0,1)
116            // Minimum vertex cover K* = 1 (either {0} or {1})
117            // Budget = 2 + 1 = 3, universe_size = 3, a₀ = 2
118            // Subsets = {{0,1,2}}
119            // Optimal sequence length = K* + |E| = 1 + 1 = 2
120            let source = MinimumVertexCover::new(SimpleGraph::new(2, vec![(0, 1)]), vec![One; 2]);
121
122            // Optimal sequence for cover {0} (2 steps):
123            // Step 0: {a₀=2} ∪ {0} → z₀ = {0,2}   operands: (2, 0)
124            // Step 1: {1} ∪ z₀ → z₁ = {0,1,2} ✓    operands: (1, 3) where 3 = universe_size + 0
125            // Step 2: padding (unused)                operands: (2, 1)
126            let target_config = vec![
127                2, 0, // step 0: {a₀} ∪ {0}
128                1, 3, // step 1: {1} ∪ z₀
129                2, 1, // step 2: padding
130            ];
131            // Extraction picks up vertices 0 (step 0) and 1 (step 1) from the
132            // 2 meaningful steps. Step 2 is padding and is ignored.
133            // Cover {0,1} is valid (though not minimum — the optimal witness
134            // is found by BruteForce, giving cover {0} or {1}).
135            let source_config = vec![1, 1];
136
137            crate::example_db::specs::rule_example_with_witness::<_, EnsembleComputation>(
138                source,
139                SolutionPair {
140                    source_config,
141                    target_config,
142                },
143            )
144        },
145    }]
146}
147
148#[cfg(test)]
149#[path = "../unit_tests/rules/minimumvertexcover_ensemblecomputation.rs"]
150mod tests;
problemreductions/rules/minimumvertexcover_ensemblecomputation.rs

problemreductions/rules/
minimumvertexcover_ensemblecomputation.rs
