problemreductions/rules/
coloring_qubo.rs

1//! Reduction from KColoring to QUBO.
2//!
3//! One-hot encoding: x_{v,c} = 1 iff vertex v gets color c.
4//! QUBO variable index: v * K + c.
5//!
6//! One-hot penalty: P1*sum_v (1 - sum_c x_{v,c})^2
7//! Edge penalty: P2*sum_{(u,v) in E} sum_c x_{u,c}*x_{v,c}
8//!
9//! QUBO has n*K variables.
10
11use crate::models::algebraic::QUBO;
12use crate::models::graph::KColoring;
13use crate::reduction;
14use crate::rules::traits::{ReduceTo, ReductionResult};
15use crate::topology::{Graph, SimpleGraph};
16use crate::variant::{KValue, K2, K3, KN};
17
18/// Result of reducing KColoring to QUBO.
19#[derive(Debug, Clone)]
20pub struct ReductionKColoringToQUBO<K: KValue> {
21    target: QUBO<f64>,
22    num_vertices: usize,
23    num_colors: usize,
24    _phantom: std::marker::PhantomData<K>,
25}
26
27impl<K: KValue> ReductionResult for ReductionKColoringToQUBO<K> {
28    type Source = KColoring<K, SimpleGraph>;
29    type Target = QUBO<f64>;
30
31    fn target_problem(&self) -> &Self::Target {
32        &self.target
33    }
34
35    /// Decode one-hot: for each vertex, find which color bit is 1.
36    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
37        let k = self.num_colors;
38        (0..self.num_vertices)
39            .map(|v| {
40                (0..k)
41                    .find(|&c| target_solution[v * k + c] == 1)
42                    .unwrap_or(0)
43            })
44            .collect()
45    }
46}
47
48/// Helper function implementing the KColoring to QUBO reduction logic.
49fn reduce_kcoloring_to_qubo<K: KValue>(
50    problem: &KColoring<K, SimpleGraph>,
51) -> ReductionKColoringToQUBO<K> {
52    let k = problem.num_colors();
53    let n = problem.graph().num_vertices();
54    let edges = problem.graph().edges();
55    let nq = n * k;
56
57    // Penalty must be large enough to enforce one-hot constraints
58    // P1 for one-hot, P2 for edge conflicts; use same penalty
59    let penalty = 1.0 + n as f64;
60
61    let mut matrix = vec![vec![0.0; nq]; nq];
62
63    // One-hot penalty: P1*sum_v (1 - sum_c x_{v,c})^2
64    // Expanding: (1 - sum_c x_{v,c})^2 = 1 - 2*sum_c x_{v,c} + (sum_c x_{v,c})^2
65    // = 1 - 2*sum_c x_{v,c} + sum_c x_{v,c}^2 + 2*sum_{c<c'} x_{v,c}*x_{v,c'}
66    // Since x^2 = x for binary: = 1 - sum_c x_{v,c} + 2*sum_{c<c'} x_{v,c}*x_{v,c'}
67    for v in 0..n {
68        for c in 0..k {
69            let idx = v * k + c;
70            // Diagonal: -P1 (from the linear term -sum_c x_{v,c})
71            matrix[idx][idx] -= penalty;
72        }
73        // Off-diagonal within same vertex: 2*P1 for each pair of colors
74        for c1 in 0..k {
75            for c2 in (c1 + 1)..k {
76                let idx1 = v * k + c1;
77                let idx2 = v * k + c2;
78                matrix[idx1][idx2] += 2.0 * penalty;
79            }
80        }
81    }
82
83    // Edge penalty: P2*sum_{(u,v) in E} sum_c x_{u,c}*x_{v,c}
84    let edge_penalty = penalty / 2.0;
85    for (u, v) in &edges {
86        for c in 0..k {
87            let idx_u = u * k + c;
88            let idx_v = v * k + c;
89            let (i, j) = if idx_u < idx_v {
90                (idx_u, idx_v)
91            } else {
92                (idx_v, idx_u)
93            };
94            matrix[i][j] += edge_penalty;
95        }
96    }
97
98    ReductionKColoringToQUBO {
99        target: QUBO::from_matrix(matrix),
100        num_vertices: n,
101        num_colors: k,
102        _phantom: std::marker::PhantomData,
103    }
104}
105
106// Register only the KN variant in the reduction graph
107#[reduction(
108    overhead = { num_vars = "num_vertices^2" }
109)]
110impl ReduceTo<QUBO<f64>> for KColoring<KN, SimpleGraph> {
111    type Result = ReductionKColoringToQUBO<KN>;
112
113    fn reduce_to(&self) -> Self::Result {
114        reduce_kcoloring_to_qubo(self)
115    }
116}
117
118// Additional concrete impls for tests (not registered in reduction graph)
119macro_rules! impl_kcoloring_to_qubo {
120    ($($ktype:ty),+) => {$(
121        impl ReduceTo<QUBO<f64>> for KColoring<$ktype, SimpleGraph> {
122            type Result = ReductionKColoringToQUBO<$ktype>;
123            fn reduce_to(&self) -> Self::Result { reduce_kcoloring_to_qubo(self) }
124        }
125    )+};
126}
127
128impl_kcoloring_to_qubo!(K2, K3);
129
130#[cfg(test)]
131#[path = "../unit_tests/rules/coloring_qubo.rs"]
132mod tests;
problemreductions/rules/coloring_qubo.rs

problemreductions/rules/
coloring_qubo.rs
