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::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
36#[reduction(
37    overhead = {
38        num_vertices = "num_vertices",
39        num_edges = "num_vertices * (num_vertices - 1) / 2 - num_edges",
40    }
41)]
42impl ReduceTo<MaximumClique<SimpleGraph, i32>> for MaximumIndependentSet<SimpleGraph, i32> {
43    type Result = ReductionISToClique<i32>;
44
45    fn reduce_to(&self) -> Self::Result {
46        let n = self.graph().num_vertices();
47        // Build complement graph edges
48        let mut complement_edges = Vec::new();
49        for u in 0..n {
50            for v in (u + 1)..n {
51                if !self.graph().has_edge(u, v) {
52                    complement_edges.push((u, v));
53                }
54            }
55        }
56        let target = MaximumClique::new(
57            SimpleGraph::new(n, complement_edges),
58            self.weights().to_vec(),
59        );
60        ReductionISToClique { target }
61    }
62}
63
64#[cfg(test)]
65#[path = "../unit_tests/rules/maximumindependentset_maximumclique.rs"]
66mod tests;
problemreductions/rules/maximumindependentset_maximumclique.rs

problemreductions/rules/
maximumindependentset_maximumclique.rs
