problemreductions/rules/
kcoloring_twodimensionalconsecutivesets.rs

1//! Reduction from KColoring (K3) to TwoDimensionalConsecutiveSets.
2//!
3//! Given a graph G = (V, E) with |V| = n and |E| = m, construct:
4//!
5//! - Alphabet: V union {d_e : e in E}, size n + m
6//! - For each edge e = {u, v}, one subset {u, v, d_e} of size 3
7//!
8//! A valid 3-coloring corresponds to a partition into 3 groups where each
9//! edge-subset spans 3 consecutive groups with one element per group.
10//!
11//! Reference: Garey & Johnson, Appendix A4.2, p.230 (Lipski 1977).
12
13use crate::models::graph::KColoring;
14use crate::models::set::TwoDimensionalConsecutiveSets;
15use crate::reduction;
16use crate::rules::traits::{ReduceTo, ReductionResult};
17use crate::topology::{Graph, SimpleGraph};
18use crate::variant::K3;
19
20/// Result of reducing KColoring<K3> to TwoDimensionalConsecutiveSets.
21#[derive(Debug, Clone)]
22pub struct ReductionKColoringToTDCS {
23    target: TwoDimensionalConsecutiveSets,
24    /// Number of vertices in the source graph.
25    num_vertices: usize,
26}
27
28impl ReductionResult for ReductionKColoringToTDCS {
29    type Source = KColoring<K3, SimpleGraph>;
30    type Target = TwoDimensionalConsecutiveSets;
31
32    fn target_problem(&self) -> &Self::Target {
33        &self.target
34    }
35
36    /// Extract a 3-coloring from a TwoDimensionalConsecutiveSets solution.
37    ///
38    /// The target solution assigns each alphabet symbol to a group index.
39    /// The first `num_vertices` symbols correspond to graph vertices,
40    /// so their group assignments directly give a valid 3-coloring
41    /// (after remapping to colors 0, 1, 2).
42    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
43        // The target solution is config[symbol] = group_index.
44        // Vertex symbols are indices 0..num_vertices.
45        // We need to remap the group indices to colors 0, 1, 2.
46        // The target may use any labels, so we compress the distinct
47        // group indices used by vertex symbols to 0..2.
48
49        let vertex_groups = &target_solution[..self.num_vertices];
50
51        // Collect distinct group indices used by vertices and map to 0..k-1
52        let mut used: Vec<usize> = vertex_groups.to_vec();
53        used.sort();
54        used.dedup();
55
56        let group_to_color: std::collections::HashMap<usize, usize> = used
57            .into_iter()
58            .enumerate()
59            .map(|(color, group)| (group, color % 3))
60            .collect();
61
62        vertex_groups.iter().map(|&g| group_to_color[&g]).collect()
63    }
64}
65
66#[reduction(
67    overhead = {
68        alphabet_size = "num_vertices + num_edges",
69        num_subsets = "num_edges",
70    }
71)]
72impl ReduceTo<TwoDimensionalConsecutiveSets> for KColoring<K3, SimpleGraph> {
73    type Result = ReductionKColoringToTDCS;
74
75    fn reduce_to(&self) -> Self::Result {
76        let n = self.graph().num_vertices();
77        let edges: Vec<(usize, usize)> = self.graph().edges();
78        let m = edges.len();
79        let alphabet_size = n + m;
80
81        // For each edge e_i = {u, v}, create subset {u, v, n + i}
82        let subsets: Vec<Vec<usize>> = edges
83            .iter()
84            .enumerate()
85            .map(|(i, &(u, v))| vec![u, v, n + i])
86            .collect();
87
88        let target = TwoDimensionalConsecutiveSets::new(alphabet_size, subsets);
89
90        ReductionKColoringToTDCS {
91            target,
92            num_vertices: n,
93        }
94    }
95}
96
97#[cfg(feature = "example-db")]
98pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
99    use crate::export::SolutionPair;
100    use crate::traits::Problem;
101
102    vec![crate::example_db::specs::RuleExampleSpec {
103        id: "kcoloring_to_twodimensionalconsecutivesets",
104        build: || {
105            // Small 3-colorable graph: triangle with pendant
106            // 0 -- 1 -- 2 -- 0, plus 2 -- 3
107            // 3-coloring: 0->0, 1->1, 2->2, 3->0
108            let source =
109                KColoring::<K3, _>::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (0, 2), (2, 3)]));
110            let reduction = <KColoring<K3, SimpleGraph> as ReduceTo<
111                TwoDimensionalConsecutiveSets,
112            >>::reduce_to(&source);
113            let target = reduction.target_problem();
114
115            // Source coloring: 0->0, 1->1, 2->2, 3->0
116            // Target config: vertex 0->group 0, vertex 1->group 1, vertex 2->group 2, vertex 3->group 0
117            // Dummies:
118            //   d_{0,1} (symbol 4): colors used {0,1}, dummy->group 2
119            //   d_{1,2} (symbol 5): colors used {1,2}, dummy->group 0
120            //   d_{0,2} (symbol 6): colors used {0,2}, dummy->group 1
121            //   d_{2,3} (symbol 7): colors used {2,0}, dummy->group 1
122            let source_config = vec![0, 1, 2, 0];
123            let target_config = vec![0, 1, 2, 0, 2, 0, 1, 1];
124
125            // Verify the target config is valid
126            assert!(
127                target.evaluate(&target_config).0,
128                "canonical example target config must be valid"
129            );
130
131            crate::example_db::specs::assemble_rule_example(
132                &source,
133                target,
134                vec![SolutionPair {
135                    source_config,
136                    target_config,
137                }],
138            )
139        },
140    }]
141}
142
143#[cfg(test)]
144#[path = "../unit_tests/rules/kcoloring_twodimensionalconsecutivesets.rs"]
145mod tests;
problemreductions/rules/kcoloring_twodimensionalconsecutivesets.rs

problemreductions/rules/
kcoloring_twodimensionalconsecutivesets.rs
