problemreductions/rules/
vertexcovering_independentset.rs

1//! Reductions between IndependentSet and VertexCovering problems.
2//!
3//! These problems are complements: a set S is an independent set iff V\S is a vertex cover.
4
5use crate::models::graph::{IndependentSet, VertexCovering};
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::traits::Problem;
8use crate::types::ProblemSize;
9use num_traits::{Num, Zero};
10use std::ops::AddAssign;
11
12/// Result of reducing IndependentSet to VertexCovering.
13#[derive(Debug, Clone)]
14pub struct ReductionISToVC<W> {
15    target: VertexCovering<W>,
16    source_size: ProblemSize,
17}
18
19impl<W> ReductionResult for ReductionISToVC<W>
20where
21    W: Clone + Default + PartialOrd + Num + Zero + AddAssign + 'static,
22{
23    type Source = IndependentSet<W>;
24    type Target = VertexCovering<W>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    /// Solution extraction: complement the configuration.
31    /// If v is in the independent set (1), it's NOT in the vertex cover (0).
32    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
33        target_solution.iter().map(|&x| 1 - x).collect()
34    }
35
36    fn source_size(&self) -> ProblemSize {
37        self.source_size.clone()
38    }
39
40    fn target_size(&self) -> ProblemSize {
41        self.target.problem_size()
42    }
43}
44
45impl<W> ReduceTo<VertexCovering<W>> for IndependentSet<W>
46where
47    W: Clone + Default + PartialOrd + Num + Zero + AddAssign + From<i32> + 'static,
48{
49    type Result = ReductionISToVC<W>;
50
51    fn reduce_to(&self) -> Self::Result {
52        let target = VertexCovering::with_weights(
53            self.num_vertices(),
54            self.edges(),
55            self.weights_ref().clone(),
56        );
57        ReductionISToVC {
58            target,
59            source_size: self.problem_size(),
60        }
61    }
62}
63
64/// Result of reducing VertexCovering to IndependentSet.
65#[derive(Debug, Clone)]
66pub struct ReductionVCToIS<W> {
67    target: IndependentSet<W>,
68    source_size: ProblemSize,
69}
70
71impl<W> ReductionResult for ReductionVCToIS<W>
72where
73    W: Clone + Default + PartialOrd + Num + Zero + AddAssign + 'static,
74{
75    type Source = VertexCovering<W>;
76    type Target = IndependentSet<W>;
77
78    fn target_problem(&self) -> &Self::Target {
79        &self.target
80    }
81
82    /// Solution extraction: complement the configuration.
83    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
84        target_solution.iter().map(|&x| 1 - x).collect()
85    }
86
87    fn source_size(&self) -> ProblemSize {
88        self.source_size.clone()
89    }
90
91    fn target_size(&self) -> ProblemSize {
92        self.target.problem_size()
93    }
94}
95
96impl<W> ReduceTo<IndependentSet<W>> for VertexCovering<W>
97where
98    W: Clone + Default + PartialOrd + Num + Zero + AddAssign + From<i32> + 'static,
99{
100    type Result = ReductionVCToIS<W>;
101
102    fn reduce_to(&self) -> Self::Result {
103        let target = IndependentSet::with_weights(
104            self.num_vertices(),
105            self.edges(),
106            self.weights_ref().clone(),
107        );
108        ReductionVCToIS {
109            target,
110            source_size: self.problem_size(),
111        }
112    }
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118    use crate::solvers::{BruteForce, Solver};
119
120    #[test]
121    fn test_is_to_vc_reduction() {
122        // Triangle graph: max IS = 1, min VC = 2
123        let is_problem = IndependentSet::<i32>::new(3, vec![(0, 1), (1, 2), (0, 2)]);
124        let reduction = ReduceTo::<VertexCovering<i32>>::reduce_to(&is_problem);
125        let vc_problem = reduction.target_problem();
126
127        // Solve the VC problem
128        let solver = BruteForce::new();
129        let vc_solutions = solver.find_best(vc_problem);
130
131        // Extract back to IS solutions
132        let is_solutions: Vec<_> = vc_solutions
133            .iter()
134            .map(|s| reduction.extract_solution(s))
135            .collect();
136
137        // Verify IS solutions are valid and optimal
138        for sol in &is_solutions {
139            let size: usize = sol.iter().sum();
140            assert_eq!(size, 1, "Max IS in triangle should be 1");
141        }
142    }
143
144    #[test]
145    fn test_vc_to_is_reduction() {
146        // Path graph 0-1-2: min VC = 1 (just vertex 1), max IS = 2 (vertices 0 and 2)
147        let vc_problem = VertexCovering::<i32>::new(3, vec![(0, 1), (1, 2)]);
148        let reduction = ReduceTo::<IndependentSet<i32>>::reduce_to(&vc_problem);
149        let is_problem = reduction.target_problem();
150
151        let solver = BruteForce::new();
152        let is_solutions = solver.find_best(is_problem);
153
154        let vc_solutions: Vec<_> = is_solutions
155            .iter()
156            .map(|s| reduction.extract_solution(s))
157            .collect();
158
159        // Verify VC solutions
160        for sol in &vc_solutions {
161            let size: usize = sol.iter().sum();
162            assert_eq!(size, 1, "Min VC in path should be 1");
163        }
164    }
165
166    #[test]
167    fn test_roundtrip_is_vc_is() {
168        let original = IndependentSet::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);
169        let solver = BruteForce::new();
170        let original_solutions = solver.find_best(&original);
171
172        // IS -> VC -> IS
173        let reduction1 = ReduceTo::<VertexCovering<i32>>::reduce_to(&original);
174        let vc = reduction1.target_problem().clone();
175        let reduction2 = ReduceTo::<IndependentSet<i32>>::reduce_to(&vc);
176        let roundtrip = reduction2.target_problem();
177
178        let roundtrip_solutions = solver.find_best(roundtrip);
179
180        // Solutions should have same objective value
181        let orig_size: usize = original_solutions[0].iter().sum();
182        let rt_size: usize = roundtrip_solutions[0].iter().sum();
183        assert_eq!(orig_size, rt_size);
184    }
185
186    #[test]
187    fn test_weighted_reduction() {
188        // Test with weighted problems
189        let is_problem =
190            IndependentSet::with_weights(3, vec![(0, 1), (1, 2)], vec![10, 20, 30]);
191        let reduction = ReduceTo::<VertexCovering<i32>>::reduce_to(&is_problem);
192        let vc_problem = reduction.target_problem();
193
194        // Weights should be preserved
195        assert_eq!(vc_problem.weights_ref(), &vec![10, 20, 30]);
196    }
197
198    #[test]
199    fn test_source_and_target_size() {
200        let is_problem = IndependentSet::<i32>::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]);
201        let reduction = ReduceTo::<VertexCovering<i32>>::reduce_to(&is_problem);
202
203        let source_size = reduction.source_size();
204        let target_size = reduction.target_size();
205
206        assert_eq!(source_size.get("num_vertices"), Some(5));
207        assert_eq!(target_size.get("num_vertices"), Some(5));
208    }
209}
210
211// Register reductions with inventory for auto-discovery
212use crate::poly;
213use crate::rules::registry::{ReductionEntry, ReductionOverhead};
214
215inventory::submit! {
216    ReductionEntry {
217        source_name: "IndependentSet",
218        target_name: "VertexCovering",
219        source_graph: "SimpleGraph",
220        target_graph: "SimpleGraph",
221        overhead_fn: || ReductionOverhead::new(vec![
222            ("num_vertices", poly!(num_vertices)),
223            ("num_edges", poly!(num_edges)),
224        ]),
225    }
226}
227
228inventory::submit! {
229    ReductionEntry {
230        source_name: "VertexCovering",
231        target_name: "IndependentSet",
232        source_graph: "SimpleGraph",
233        target_graph: "SimpleGraph",
234        overhead_fn: || ReductionOverhead::new(vec![
235            ("num_vertices", poly!(num_vertices)),
236            ("num_edges", poly!(num_edges)),
237        ]),
238    }
239}
problemreductions/rules/vertexcovering_independentset.rs

problemreductions/rules/
vertexcovering_independentset.rs
