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(test)]
95#[path = "../unit_tests/rules/minimumvertexcover_maximumindependentset.rs"]
96mod tests;
problemreductions/rules/minimumvertexcover_maximumindependentset.rs

problemreductions/rules/
minimumvertexcover_maximumindependentset.rs
