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 extends to at most three groups. Conversely, each edge
9//! triple spans three consecutive groups. After retaining only vertex groups,
10//! endpoint ranks differ by one or two, so rank modulo three gives a coloring.
11//! Empty sources map to a one-symbol YES instance; loops to a fixed NO instance.
12//!
13//! Definition: Lipski, CSL Report T-67 (1978), Problem 5; see the paper for proof.
14
15use crate::models::graph::KColoring;
16use crate::models::set::TwoDimensionalConsecutiveSets;
17use crate::reduction;
18use crate::rules::traits::{ReduceTo, ReductionResult};
19use crate::topology::{Graph, SimpleGraph};
20use crate::variant::K3;
21
22/// Result of reducing KColoring<K3> to TwoDimensionalConsecutiveSets.
23#[derive(Debug, Clone)]
24pub struct ReductionKColoringToTDCS {
25    target: TwoDimensionalConsecutiveSets,
26    /// Number of vertices in the source graph.
27    num_vertices: usize,
28}
29
30impl ReductionResult for ReductionKColoringToTDCS {
31    type Source = KColoring<K3, SimpleGraph>;
32    type Target = TwoDimensionalConsecutiveSets;
33
34    fn target_problem(&self) -> &Self::Target {
35        &self.target
36    }
37
38    /// Extract a 3-coloring from a TwoDimensionalConsecutiveSets solution.
39    ///
40    /// The target solution assigns each alphabet symbol to a group index.
41    /// The first `num_vertices` symbols correspond to graph vertices,
42    /// so their group assignments directly give a valid 3-coloring
43    /// (after remapping to colors 0, 1, 2).
44    fn extract_solution(
45        &self,
46        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
47    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
48        crate::rules::traits::validate_target_witness(
49            self.target_problem(),
50            target_solution,
51            |value| value.0,
52            "target grouping is not a consecutive-set partition",
53        )?;
54
55        Ok({
56            // The target solution is config[symbol] = group_index.
57            // Vertex symbols are indices 0..num_vertices.
58            // Removing dummy-only groups cannot increase the separation of
59            // edge endpoints: their distinct ranks differ by one or two.
60            // Taking these ranks modulo three therefore preserves every edge.
61
62            let vertex_groups = &target_solution[..self.num_vertices];
63
64            // Collect distinct group indices used by vertices and map to 0..k-1
65            let mut used: Vec<usize> = vertex_groups.to_vec();
66            used.sort();
67            used.dedup();
68
69            let group_to_color: std::collections::HashMap<usize, usize> = used
70                .into_iter()
71                .enumerate()
72                .map(|(color, group)| (group, color % 3))
73                .collect();
74
75            vertex_groups.iter().map(|&g| group_to_color[&g]).collect()
76        })
77    }
78}
79
80#[crate::aggregate_reduction(identity)]
81impl crate::rules::AggregateReductionResult for ReductionKColoringToTDCS {}
82
83#[reduction(
84    transform = upper_bound {
85        alphabet_size = "num_vertices + num_edges + 3",
86        num_subsets = "num_edges + 3",
87    }
88)]
89impl ReduceTo<TwoDimensionalConsecutiveSets> for KColoring<K3, SimpleGraph> {
90    type Result = ReductionKColoringToTDCS;
91
92    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
93        let n = self.graph().num_vertices();
94        let edges: Vec<(usize, usize)> = self.graph().edges();
95        let m = edges.len();
96        let (alphabet_size, subsets) = if edges.iter().any(|&(u, v)| u == v) {
97            // Three symbols cannot occupy pairwise consecutive distinct groups:
98            // the first and last groups are not adjacent. This is a fixed NO.
99            (3, vec![vec![0, 1], vec![1, 2], vec![0, 2]])
100        } else {
101            // Native node and edge Vec allocation bounds make n + m fit usize.
102            let alphabet_size = n + m;
103            let subsets = edges
104                .iter()
105                .enumerate()
106                .map(|(i, &(u, v))| vec![u, v, n + i])
107                .collect();
108            // The empty graph is colorable, while the target requires a
109            // positive alphabet. One unconstrained symbol preserves YES.
110            (alphabet_size.max(1), subsets)
111        };
112        let target = TwoDimensionalConsecutiveSets::try_new(alphabet_size, subsets).map_err(
113            crate::rules::ReductionError::construction::<Self, TwoDimensionalConsecutiveSets>,
114        )?;
115
116        Ok(ReductionKColoringToTDCS {
117            target,
118            num_vertices: n,
119        })
120    }
121}
122
123#[cfg(feature = "example-db")]
124pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
125    use crate::export::SolutionPair;
126    use crate::traits::Problem;
127
128    vec![crate::example_db::specs::RuleExampleSpec {
129        id: "kcoloring_to_twodimensionalconsecutivesets",
130        build: || {
131            // Small 3-colorable graph: triangle with pendant
132            // 0 -- 1 -- 2 -- 0, plus 2 -- 3
133            // 3-coloring: 0->0, 1->1, 2->2, 3->0
134            let source =
135                KColoring::<K3, _>::new(SimpleGraph::new(4, vec![(0, 1), (1, 2), (0, 2), (2, 3)]));
136            let reduction = <KColoring<K3, SimpleGraph> as ReduceTo<
137                TwoDimensionalConsecutiveSets,
138            >>::reduce_to(&source)
139            .expect("reduction should succeed");
140            let target = reduction.target_problem();
141
142            // Source coloring: 0->0, 1->1, 2->2, 3->0
143            // Target config: vertex 0->group 0, vertex 1->group 1, vertex 2->group 2, vertex 3->group 0
144            // Dummies:
145            //   d_{0,1} (symbol 4): colors used {0,1}, dummy->group 2
146            //   d_{1,2} (symbol 5): colors used {1,2}, dummy->group 0
147            //   d_{0,2} (symbol 6): colors used {0,2}, dummy->group 1
148            //   d_{2,3} (symbol 7): colors used {2,0}, dummy->group 1
149            let source_config = vec![0, 1, 2, 0];
150            let target_config = vec![0, 1, 2, 0, 2, 0, 1, 1];
151
152            // Verify the target config is valid
153            assert!(
154                target
155                    .evaluate(&target_config)
156                    .expect("canonical target evaluation must succeed")
157                    .0,
158                "canonical example target config must be valid"
159            );
160
161            crate::example_db::specs::assemble_rule_example(
162                &source,
163                target,
164                vec![SolutionPair {
165                    source_config: serde_json::to_value(source_config)
166                        .expect("solution serialization must succeed"),
167                    target_config: serde_json::to_value(target_config)
168                        .expect("solution serialization must succeed"),
169                }],
170            )
171        },
172    }]
173}
174
175#[cfg(test)]
176#[path = "../unit_tests/rules/kcoloring_twodimensionalconsecutivesets.rs"]
177mod tests;
problemreductions/rules/kcoloring_twodimensionalconsecutivesets.rs

problemreductions/rules/
kcoloring_twodimensionalconsecutivesets.rs
