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(&self, target_solution: &[usize]) -> Vec<usize> {
32        target_solution.to_vec()
33    }
34}
35
36fn reduce_clique_to_is<W: WeightElement>(
37    src: &MaximumClique<SimpleGraph, W>,
38) -> ReductionCliqueToIS<W> {
39    let comp_edges = super::graph_helpers::complement_edges(src.graph());
40    let target = MaximumIndependentSet::new(
41        SimpleGraph::new(src.graph().num_vertices(), comp_edges),
42        src.weights().to_vec(),
43    );
44    ReductionCliqueToIS { target }
45}
46
47#[reduction(
48    overhead = {
49        num_vertices = "num_vertices",
50        num_edges = "num_vertices * (num_vertices - 1) / 2 - num_edges",
51    }
52)]
53impl ReduceTo<MaximumIndependentSet<SimpleGraph, i32>> for MaximumClique<SimpleGraph, i32> {
54    type Result = ReductionCliqueToIS<i32>;
55
56    fn reduce_to(&self) -> Self::Result {
57        reduce_clique_to_is(self)
58    }
59}
60
61#[reduction(
62    overhead = {
63        num_vertices = "num_vertices",
64        num_edges = "num_vertices * (num_vertices - 1) / 2 - num_edges",
65    }
66)]
67impl ReduceTo<MaximumIndependentSet<SimpleGraph, One>> for MaximumClique<SimpleGraph, One> {
68    type Result = ReductionCliqueToIS<One>;
69
70    fn reduce_to(&self) -> Self::Result {
71        reduce_clique_to_is(self)
72    }
73}
74
75#[cfg(feature = "example-db")]
76pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
77    use crate::export::SolutionPair;
78
79    vec![
80        crate::example_db::specs::RuleExampleSpec {
81            id: "maximumclique_to_maximumindependentset",
82            build: || {
83                let source = MaximumClique::new(
84                    SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
85                    vec![1i32; 4],
86                );
87                crate::example_db::specs::rule_example_with_witness::<
88                    _,
89                    MaximumIndependentSet<SimpleGraph, i32>,
90                >(
91                    source,
92                    SolutionPair {
93                        source_config: vec![0, 1, 1, 0],
94                        target_config: vec![0, 1, 1, 0],
95                    },
96                )
97            },
98        },
99        crate::example_db::specs::RuleExampleSpec {
100            id: "maximumclique_to_maximumindependentset_one",
101            build: || {
102                let source = MaximumClique::new(
103                    SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
104                    vec![One; 4],
105                );
106                crate::example_db::specs::rule_example_with_witness::<
107                    _,
108                    MaximumIndependentSet<SimpleGraph, One>,
109                >(
110                    source,
111                    SolutionPair {
112                        source_config: vec![0, 1, 1, 0],
113                        target_config: vec![0, 1, 1, 0],
114                    },
115                )
116            },
117        },
118    ]
119}
120
121#[cfg(test)]
122#[path = "../unit_tests/rules/maximumclique_maximumindependentset.rs"]
123mod tests;
problemreductions/rules/maximumclique_maximumindependentset.rs

problemreductions/rules/
maximumclique_maximumindependentset.rs
