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(&self, target_solution: &[usize]) -> Vec<usize> {
32        target_solution.to_vec()
33    }
34}
35
36fn reduce_is_to_clique<W: WeightElement>(
37    src: &MaximumIndependentSet<SimpleGraph, W>,
38) -> ReductionISToClique<W> {
39    let comp_edges = super::graph_helpers::complement_edges(src.graph());
40    let target = MaximumClique::new(
41        SimpleGraph::new(src.graph().num_vertices(), comp_edges),
42        src.weights().to_vec(),
43    );
44    ReductionISToClique { 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<MaximumClique<SimpleGraph, i32>> for MaximumIndependentSet<SimpleGraph, i32> {
54    type Result = ReductionISToClique<i32>;
55
56    fn reduce_to(&self) -> Self::Result {
57        reduce_is_to_clique(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<MaximumClique<SimpleGraph, One>> for MaximumIndependentSet<SimpleGraph, One> {
68    type Result = ReductionISToClique<One>;
69
70    fn reduce_to(&self) -> Self::Result {
71        reduce_is_to_clique(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: "maximumindependentset_to_maximumclique",
82            build: || {
83                let source = MaximumIndependentSet::new(
84                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
85                    vec![1i32; 5],
86                );
87                crate::example_db::specs::rule_example_with_witness::<
88                    _,
89                    MaximumClique<SimpleGraph, i32>,
90                >(
91                    source,
92                    SolutionPair {
93                        source_config: vec![1, 0, 1, 0, 1],
94                        target_config: vec![1, 0, 1, 0, 1],
95                    },
96                )
97            },
98        },
99        crate::example_db::specs::RuleExampleSpec {
100            id: "maximumindependentset_to_maximumclique_one",
101            build: || {
102                let source = MaximumIndependentSet::new(
103                    SimpleGraph::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]),
104                    vec![One; 5],
105                );
106                crate::example_db::specs::rule_example_with_witness::<
107                    _,
108                    MaximumClique<SimpleGraph, One>,
109                >(
110                    source,
111                    SolutionPair {
112                        source_config: vec![1, 0, 1, 0, 1],
113                        target_config: vec![1, 0, 1, 0, 1],
114                    },
115                )
116            },
117        },
118    ]
119}
120
121#[cfg(test)]
122#[path = "../unit_tests/rules/maximumindependentset_maximumclique.rs"]
123mod tests;
problemreductions/rules/maximumindependentset_maximumclique.rs

problemreductions/rules/
maximumindependentset_maximumclique.rs
