problemreductions/rules/
maximumindependentset_maximumclique.rs

1//! Reduction from MaximumIndependentSet to MaximumClique via complement graph.
2//!
3//! An independent set in G corresponds to a clique in the complement graph Ḡ.
4//! This is Karp's classical complement graph reduction.
5
6use crate::models::graph::{MaximumClique, MaximumIndependentSet};
7use crate::reduction;
8use crate::rules::traits::{ReduceTo, ReductionResult};
9use crate::topology::{Graph, SimpleGraph};
10use crate::types::{One, WeightElement};
11
12/// Result of reducing MaximumIndependentSet to MaximumClique.
13#[derive(Debug, Clone)]
14pub struct ReductionISToClique<W> {
15    target: MaximumClique<SimpleGraph, W>,
16}
17
18impl<W> ReductionResult for ReductionISToClique<W>
19where
20    W: WeightElement + crate::variant::VariantParam,
21{
22    type Source = MaximumIndependentSet<SimpleGraph, W>;
23    type Target = MaximumClique<SimpleGraph, W>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    /// Solution extraction: identity mapping.
30    /// A vertex selected in the clique (target) is also selected in the independent set (source).
31    fn extract_solution(
32        &self,
33        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
34    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
35        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
36
37        Ok(target_solution.to_vec())
38    }
39}
40
41fn reduce_is_to_clique<W: WeightElement>(
42    src: &MaximumIndependentSet<SimpleGraph, W>,
43) -> ReductionISToClique<W> {
44    let comp_edges = super::graph_helpers::complement_edges(src.graph());
45    let target = MaximumClique::new(
46        SimpleGraph::new(src.graph().num_vertices(), comp_edges),
47        src.weights().to_vec(),
48    );
49    ReductionISToClique { target }
50}
51
52#[reduction(
53    transform = exact {
54        num_vertices = "num_vertices",
55        num_edges = "num_vertices * (num_vertices - 1) / 2 - num_edges",
56    }
57)]
58impl ReduceTo<MaximumClique<SimpleGraph, i64>> for MaximumIndependentSet<SimpleGraph, i64> {
59    type Result = ReductionISToClique<i64>;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        Ok(reduce_is_to_clique(self))
63    }
64}
65
66#[reduction(
67    transform = exact {
68        num_vertices = "num_vertices",
69        num_edges = "num_vertices * (num_vertices - 1) / 2 - num_edges",
70    }
71)]
72impl ReduceTo<MaximumClique<SimpleGraph, One>> for MaximumIndependentSet<SimpleGraph, One> {
73    type Result = ReductionISToClique<One>;
74
75    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
76        Ok(reduce_is_to_clique(self))
77    }
78}
79
80#[cfg(feature = "example-db")]
81pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
82    use crate::export::SolutionPair;
83
84    vec![
85        crate::example_db::specs::RuleExampleSpec {
86            id: "weighted_maximumindependentset_to_maximumclique",
87            build: || {
88                let source = MaximumIndependentSet::new(
89                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
90                    vec![1i64; 5],
91                );
92                crate::example_db::specs::rule_example_with_witness::<
93                    _,
94                    MaximumClique<SimpleGraph, i64>,
95                >(
96                    source,
97                    SolutionPair {
98                        source_config: serde_json::json!(vec![true, false, true, false, true]),
99                        target_config: serde_json::json!(vec![true, false, true, false, true]),
100                    },
101                )
102            },
103        },
104        crate::example_db::specs::RuleExampleSpec {
105            id: "cardinality_maximumindependentset_to_maximumclique",
106            build: || {
107                let source = MaximumIndependentSet::new(
108                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
109                    vec![One; 5],
110                );
111                crate::example_db::specs::rule_example_with_witness::<
112                    _,
113                    MaximumClique<SimpleGraph, One>,
114                >(
115                    source,
116                    SolutionPair {
117                        source_config: serde_json::json!(vec![true, false, true, false, true]),
118                        target_config: serde_json::json!(vec![true, false, true, false, true]),
119                    },
120                )
121            },
122        },
123    ]
124}
125
126#[cfg(test)]
127#[path = "../unit_tests/rules/maximumindependentset_maximumclique.rs"]
128mod tests;
problemreductions/rules/maximumindependentset_maximumclique.rs

problemreductions/rules/
maximumindependentset_maximumclique.rs
