problemreductions/rules/
maximumclique_maximumindependentset.rs

1//! Reduction from MaximumClique to MaximumIndependentSet via complement graph.
2//!
3//! A clique in G corresponds to an independent set in the complement graph.
4//! This is one of Karp's classical reductions (1972).
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 MaximumClique to MaximumIndependentSet.
13#[derive(Debug, Clone)]
14pub struct ReductionCliqueToIS<W> {
15    target: MaximumIndependentSet<SimpleGraph, W>,
16}
17
18impl<W> ReductionResult for ReductionCliqueToIS<W>
19where
20    W: WeightElement + crate::variant::VariantParam,
21{
22    type Source = MaximumClique<SimpleGraph, W>;
23    type Target = MaximumIndependentSet<SimpleGraph, W>;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    /// Solution extraction: identity mapping.
30    /// A clique in G is an independent set in the complement, so the configuration is the same.
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_clique_to_is<W: WeightElement>(
42    src: &MaximumClique<SimpleGraph, W>,
43) -> ReductionCliqueToIS<W> {
44    let comp_edges = super::graph_helpers::complement_edges(src.graph());
45    let target = MaximumIndependentSet::new(
46        SimpleGraph::new(src.graph().num_vertices(), comp_edges),
47        src.weights().to_vec(),
48    );
49    ReductionCliqueToIS { 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<MaximumIndependentSet<SimpleGraph, i64>> for MaximumClique<SimpleGraph, i64> {
59    type Result = ReductionCliqueToIS<i64>;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        Ok(reduce_clique_to_is(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<MaximumIndependentSet<SimpleGraph, One>> for MaximumClique<SimpleGraph, One> {
73    type Result = ReductionCliqueToIS<One>;
74
75    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
76        Ok(reduce_clique_to_is(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_maximumclique_to_maximumindependentset",
87            build: || {
88                let source = MaximumClique::new(
89                    SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
90                    vec![1i64; 4],
91                );
92                crate::example_db::specs::rule_example_with_witness::<
93                    _,
94                    MaximumIndependentSet<SimpleGraph, i64>,
95                >(
96                    source,
97                    SolutionPair {
98                        source_config: serde_json::json!(vec![false, true, true, false]),
99                        target_config: serde_json::json!(vec![false, true, true, false]),
100                    },
101                )
102            },
103        },
104        crate::example_db::specs::RuleExampleSpec {
105            id: "cardinality_maximumclique_to_maximumindependentset",
106            build: || {
107                let source = MaximumClique::new(
108                    SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
109                    vec![One; 4],
110                );
111                crate::example_db::specs::rule_example_with_witness::<
112                    _,
113                    MaximumIndependentSet<SimpleGraph, One>,
114                >(
115                    source,
116                    SolutionPair {
117                        source_config: serde_json::json!(vec![false, true, true, false]),
118                        target_config: serde_json::json!(vec![false, true, true, false]),
119                    },
120                )
121            },
122        },
123    ]
124}
125
126#[cfg(test)]
127#[path = "../unit_tests/rules/maximumclique_maximumindependentset.rs"]
128mod tests;
problemreductions/rules/maximumclique_maximumindependentset.rs

problemreductions/rules/
maximumclique_maximumindependentset.rs
