problemreductions/rules/
minimumvertexcover_maximumindependentset.rs

1//! Reductions between MaximumIndependentSet and MinimumVertexCover 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::{MaximumIndependentSet, MinimumVertexCover};
6use crate::reduction;
7use crate::rules::traits::{ReduceTo, ReductionResult};
8use crate::topology::{Graph, SimpleGraph};
9use crate::types::WeightElement;
10
11/// Result of reducing MaximumIndependentSet to MinimumVertexCover.
12#[derive(Debug, Clone)]
13pub struct ReductionISToVC<W> {
14    target: MinimumVertexCover<SimpleGraph, W>,
15}
16
17impl<W> ReductionResult for ReductionISToVC<W>
18where
19    W: WeightElement + crate::variant::VariantParam,
20{
21    type Source = MaximumIndependentSet<SimpleGraph, W>;
22    type Target = MinimumVertexCover<SimpleGraph, W>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    /// Solution extraction: complement the configuration.
29    /// If v is in the independent set (1), it's NOT in the vertex cover (0).
30    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
31        target_solution.iter().map(|&x| 1 - x).collect()
32    }
33}
34
35#[reduction(
36    overhead = {
37        num_vertices = "num_vertices",
38        num_edges = "num_edges",
39    }
40)]
41impl ReduceTo<MinimumVertexCover<SimpleGraph, i32>> for MaximumIndependentSet<SimpleGraph, i32> {
42    type Result = ReductionISToVC<i32>;
43
44    fn reduce_to(&self) -> Self::Result {
45        let target = MinimumVertexCover::new(
46            SimpleGraph::new(self.graph().num_vertices(), self.graph().edges()),
47            self.weights().to_vec(),
48        );
49        ReductionISToVC { target }
50    }
51}
52
53/// Result of reducing MinimumVertexCover to MaximumIndependentSet.
54#[derive(Debug, Clone)]
55pub struct ReductionVCToIS<W> {
56    target: MaximumIndependentSet<SimpleGraph, W>,
57}
58
59impl<W> ReductionResult for ReductionVCToIS<W>
60where
61    W: WeightElement + crate::variant::VariantParam,
62{
63    type Source = MinimumVertexCover<SimpleGraph, W>;
64    type Target = MaximumIndependentSet<SimpleGraph, W>;
65
66    fn target_problem(&self) -> &Self::Target {
67        &self.target
68    }
69
70    /// Solution extraction: complement the configuration.
71    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
72        target_solution.iter().map(|&x| 1 - x).collect()
73    }
74}
75
76#[reduction(
77    overhead = {
78        num_vertices = "num_vertices",
79        num_edges = "num_edges",
80    }
81)]
82impl ReduceTo<MaximumIndependentSet<SimpleGraph, i32>> for MinimumVertexCover<SimpleGraph, i32> {
83    type Result = ReductionVCToIS<i32>;
84
85    fn reduce_to(&self) -> Self::Result {
86        let target = MaximumIndependentSet::new(
87            SimpleGraph::new(self.graph().num_vertices(), self.graph().edges()),
88            self.weights().to_vec(),
89        );
90        ReductionVCToIS { target }
91    }
92}
93
94#[cfg(feature = "example-db")]
95pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
96    use crate::export::SolutionPair;
97
98    fn vc_petersen() -> MinimumVertexCover<SimpleGraph, i32> {
99        let (n, edges) = crate::topology::small_graphs::petersen();
100        MinimumVertexCover::new(SimpleGraph::new(n, edges), vec![1i32; 10])
101    }
102
103    fn mis_petersen() -> MaximumIndependentSet<SimpleGraph, i32> {
104        let (n, edges) = crate::topology::small_graphs::petersen();
105        MaximumIndependentSet::new(SimpleGraph::new(n, edges), vec![1i32; 10])
106    }
107
108    vec![
109        crate::example_db::specs::RuleExampleSpec {
110            id: "maximumindependentset_to_minimumvertexcover",
111            build: || {
112                crate::example_db::specs::rule_example_with_witness::<
113                    _,
114                    MinimumVertexCover<SimpleGraph, i32>,
115                >(
116                    mis_petersen(),
117                    SolutionPair {
118                        source_config: vec![1, 0, 0, 1, 0, 0, 1, 1, 0, 0],
119                        target_config: vec![0, 1, 1, 0, 1, 1, 0, 0, 1, 1],
120                    },
121                )
122            },
123        },
124        crate::example_db::specs::RuleExampleSpec {
125            id: "minimumvertexcover_to_maximumindependentset",
126            build: || {
127                crate::example_db::specs::rule_example_with_witness::<
128                    _,
129                    MaximumIndependentSet<SimpleGraph, i32>,
130                >(
131                    vc_petersen(),
132                    SolutionPair {
133                        source_config: vec![0, 1, 1, 0, 1, 1, 0, 0, 1, 1],
134                        target_config: vec![1, 0, 0, 1, 0, 0, 1, 1, 0, 0],
135                    },
136                )
137            },
138        },
139    ]
140}
141
142#[cfg(test)]
143#[path = "../unit_tests/rules/minimumvertexcover_maximumindependentset.rs"]
144mod tests;
problemreductions/rules/minimumvertexcover_maximumindependentset.rs

problemreductions/rules/
minimumvertexcover_maximumindependentset.rs
