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}
18
19impl ReductionResult for ReductionKColoringToPartitionIntoCliques {
20    type Source = KColoring<KN, SimpleGraph>;
21    type Target = PartitionIntoCliques<SimpleGraph>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    /// Solution extraction is the identity: color classes become clique classes.
28    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
29        target_solution.to_vec()
30    }
31}
32
33#[reduction(
34    overhead = {
35        num_vertices = "num_vertices",
36        num_edges = "num_vertices * (num_vertices - 1) / 2 - num_edges",
37    }
38)]
39impl ReduceTo<PartitionIntoCliques<SimpleGraph>> for KColoring<KN, SimpleGraph> {
40    type Result = ReductionKColoringToPartitionIntoCliques;
41
42    fn reduce_to(&self) -> Self::Result {
43        let target = PartitionIntoCliques::new(
44            SimpleGraph::new(self.graph().num_vertices(), complement_edges(self.graph())),
45            self.num_colors(),
46        );
47        ReductionKColoringToPartitionIntoCliques { target }
48    }
49}
50
51#[cfg(feature = "example-db")]
52pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
53    use crate::export::SolutionPair;
54
55    vec![crate::example_db::specs::RuleExampleSpec {
56        id: "kcoloring_to_partitionintocliques",
57        build: || {
58            let source = KColoring::<KN, _>::with_k(
59                SimpleGraph::new(5, vec![(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 4)]),
60                3,
61            );
62            crate::example_db::specs::rule_example_with_witness::<
63                _,
64                PartitionIntoCliques<SimpleGraph>,
65            >(
66                source,
67                SolutionPair {
68                    source_config: vec![0, 1, 1, 0, 2],
69                    target_config: vec![0, 1, 1, 0, 2],
70                },
71            )
72        },
73    }]
74}
75
76#[cfg(test)]
77#[path = "../unit_tests/rules/kcoloring_partitionintocliques.rs"]
78mod tests;
problemreductions/rules/kcoloring_partitionintocliques.rs

problemreductions/rules/
kcoloring_partitionintocliques.rs
