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(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
35
36        Ok(target_solution.iter().map(|&x| !x).collect())
37    }
38}
39
40#[reduction(
41    transform = exact {
42        num_vertices = "num_vertices",
43        num_edges = "num_edges",
44    }
45)]
46impl ReduceTo<MinimumVertexCover<SimpleGraph, i64>> for MaximumIndependentSet<SimpleGraph, i64> {
47    type Result = ReductionISToVC<i64>;
48
49    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
50        let target = MinimumVertexCover::new(
51            SimpleGraph::new(self.graph().num_vertices(), self.graph().edges()),
52            self.weights().to_vec(),
53        );
54        Ok(ReductionISToVC { target })
55    }
56}
57
58/// Result of reducing MinimumVertexCover to MaximumIndependentSet.
59#[derive(Debug, Clone)]
60pub struct ReductionVCToIS<W> {
61    target: MaximumIndependentSet<SimpleGraph, W>,
62}
63
64impl<W> ReductionResult for ReductionVCToIS<W>
65where
66    W: WeightElement + crate::variant::VariantParam,
67{
68    type Source = MinimumVertexCover<SimpleGraph, W>;
69    type Target = MaximumIndependentSet<SimpleGraph, W>;
70
71    fn target_problem(&self) -> &Self::Target {
72        &self.target
73    }
74
75    /// Solution extraction: complement the configuration.
76    fn extract_solution(
77        &self,
78        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
79    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
80        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
81
82        Ok(target_solution.iter().map(|&x| !x).collect())
83    }
84}
85
86#[reduction(
87    transform = exact {
88        num_vertices = "num_vertices",
89        num_edges = "num_edges",
90    }
91)]
92impl ReduceTo<MaximumIndependentSet<SimpleGraph, i64>> for MinimumVertexCover<SimpleGraph, i64> {
93    type Result = ReductionVCToIS<i64>;
94
95    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
96        let target = MaximumIndependentSet::new(
97            SimpleGraph::new(self.graph().num_vertices(), self.graph().edges()),
98            self.weights().to_vec(),
99        );
100        Ok(ReductionVCToIS { target })
101    }
102}
103
104#[cfg(feature = "example-db")]
105pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
106    use crate::export::SolutionPair;
107
108    fn vc_petersen() -> MinimumVertexCover<SimpleGraph, i64> {
109        let (n, edges) = crate::topology::small_graphs::petersen();
110        MinimumVertexCover::new(SimpleGraph::new(n, edges), vec![1i64; 10])
111    }
112
113    fn mis_petersen() -> MaximumIndependentSet<SimpleGraph, i64> {
114        let (n, edges) = crate::topology::small_graphs::petersen();
115        MaximumIndependentSet::new(SimpleGraph::new(n, edges), vec![1i64; 10])
116    }
117
118    vec![
119        crate::example_db::specs::RuleExampleSpec {
120            id: "maximumindependentset_to_minimumvertexcover",
121            build: || {
122                crate::example_db::specs::rule_example_with_witness::<
123                    _,
124                    MinimumVertexCover<SimpleGraph, i64>,
125                >(
126                    mis_petersen(),
127                    SolutionPair {
128                        source_config: serde_json::json!(vec![
129                            true, false, false, true, false, false, true, true, false, false
130                        ]),
131                        target_config: serde_json::json!(vec![
132                            false, true, true, false, true, true, false, false, true, true
133                        ]),
134                    },
135                )
136            },
137        },
138        crate::example_db::specs::RuleExampleSpec {
139            id: "minimumvertexcover_to_maximumindependentset",
140            build: || {
141                crate::example_db::specs::rule_example_with_witness::<
142                    _,
143                    MaximumIndependentSet<SimpleGraph, i64>,
144                >(
145                    vc_petersen(),
146                    SolutionPair {
147                        source_config: serde_json::json!(vec![
148                            false, true, true, false, true, true, false, false, true, true
149                        ]),
150                        target_config: serde_json::json!(vec![
151                            true, false, false, true, false, false, true, true, false, false
152                        ]),
153                    },
154                )
155            },
156        },
157    ]
158}
159
160#[cfg(test)]
161#[path = "../unit_tests/rules/minimumvertexcover_maximumindependentset.rs"]
162mod tests;
problemreductions/rules/minimumvertexcover_maximumindependentset.rs

problemreductions/rules/
minimumvertexcover_maximumindependentset.rs
