problemreductions/rules/
kcoloring_partitionintocliques.rs

1//! Reduction from KColoring to PartitionIntoCliques via complement graphs.
2//!
3//! A proper k-coloring of G is exactly a partition of V into k independent
4//! sets, which become k cliques in the complement graph.
5
6use crate::models::graph::{KColoring, PartitionIntoCliques};
7use crate::reduction;
8use crate::rules::graph_helpers::complement_edges;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::variant::KN;
12
13/// Result of reducing KColoring to PartitionIntoCliques.
14#[derive(Debug, Clone)]
15pub struct ReductionKColoringToPartitionIntoCliques {
16    target: PartitionIntoCliques<SimpleGraph>,
17    source_num_vertices: usize,
18}
19
20impl ReductionResult for ReductionKColoringToPartitionIntoCliques {
21    type Source = KColoring<KN, SimpleGraph>;
22    type Target = PartitionIntoCliques<SimpleGraph>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    /// Solution extraction is the identity: color classes become clique classes.
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.0,
37            "target witness is not satisfying",
38        )?;
39
40        Ok(target_solution[..self.source_num_vertices].to_vec())
41    }
42}
43
44#[crate::aggregate_reduction(identity)]
45impl crate::rules::AggregateReductionResult for ReductionKColoringToPartitionIntoCliques {}
46
47#[reduction(
48    transform = upper_bound {
49        num_vertices = "num_vertices + 2",
50        num_edges = "num_vertices * (num_vertices - 1) / 2",
51    }
52)]
53impl ReduceTo<PartitionIntoCliques<SimpleGraph>> for KColoring<KN, SimpleGraph> {
54    type Result = ReductionKColoringToPartitionIntoCliques;
55
56    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
57        let n = self.graph().num_vertices();
58        let target = if n == 0 {
59            // The empty source is colorable; the target requires a nonempty graph.
60            PartitionIntoCliques::new(SimpleGraph::empty(1), 1)
61        } else if self.num_colors() == 0 || self.graph().edges().iter().any(|&(u, v)| u == v) {
62            // Zero colors or a loop is uncolorable; two isolated vertices do not form one clique.
63            PartitionIntoCliques::new(SimpleGraph::empty(2), 1)
64        } else {
65            PartitionIntoCliques::new(
66                SimpleGraph::new(n, complement_edges(self.graph())),
67                self.num_colors().min(n),
68            )
69        };
70        Ok(ReductionKColoringToPartitionIntoCliques {
71            target,
72            source_num_vertices: n,
73        })
74    }
75}
76
77#[cfg(feature = "example-db")]
78pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
79    use crate::export::SolutionPair;
80
81    vec![crate::example_db::specs::RuleExampleSpec {
82        id: "kcoloring_to_partitionintocliques",
83        build: || {
84            let source = KColoring::<KN, _>::with_k(
85                SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
86                3,
87            );
88            crate::example_db::specs::rule_example_with_witness::<
89                _,
90                PartitionIntoCliques<SimpleGraph>,
91            >(
92                source,
93                SolutionPair {
94                    source_config: serde_json::json!(vec![0, 1, 1, 0, 2]),
95                    target_config: serde_json::json!(vec![0, 1, 1, 0, 2]),
96                },
97            )
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/kcoloring_partitionintocliques.rs"]
104mod tests;
problemreductions/rules/kcoloring_partitionintocliques.rs

problemreductions/rules/
kcoloring_partitionintocliques.rs
