problemreductions/rules/
maxcut_minimumcutintoboundedsets.rs

1//! Reduction from MaxCut to MinimumCutIntoBoundedSets.
2//!
3//! Transforms a maximum cut problem into a minimum cut into bounded sets problem
4//! by padding to even vertex count, building a complete graph with inverted weights,
5//! and enforcing balanced bisection via size bounds.
6//!
7//! Reference: Garey, Johnson, and Stockmeyer (1976), "Some simplified NP-complete
8//! graph problems". Garey & Johnson, *Computers and Intractability*, ND17.
9
10use crate::models::graph::{MaxCut, MinimumCutIntoBoundedSets};
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14
15/// Result of reducing MaxCut to MinimumCutIntoBoundedSets.
16#[derive(Debug, Clone)]
17pub struct ReductionMaxCutToMinCutBounded {
18    target: MinimumCutIntoBoundedSets<SimpleGraph, i64>,
19    /// Number of original vertices in the source problem.
20    original_n: usize,
21}
22
23impl ReductionResult for ReductionMaxCutToMinCutBounded {
24    type Source = MaxCut<SimpleGraph, i64>;
25    type Target = MinimumCutIntoBoundedSets<SimpleGraph, i64>;
26
27    fn target_problem(&self) -> &Self::Target {
28        &self.target
29    }
30
31    /// Extract the source solution from the target balanced bisection.
32    /// Take only the first `original_n` vertex assignments.
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38
39        Ok(target_solution[..self.original_n].to_vec())
40    }
41}
42
43// With p = n + (n mod 2), the target is K_(2p): 2p vertices and p(2p-1) edges.
44// Since p <= n+1, these bounds are tight for odd n and overestimate for even n.
45#[reduction(
46    transform = upper_bound {
47        num_vertices = "2 * num_vertices + 2",
48        num_edges = "(num_vertices + 1) * (2 * num_vertices + 1)",
49    }
50)]
51impl ReduceTo<MinimumCutIntoBoundedSets<SimpleGraph, i64>> for MaxCut<SimpleGraph, i64> {
52    type Result = ReductionMaxCutToMinCutBounded;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let n = self.graph().num_vertices();
56
57        // Step 1: Pad to even vertex count.
58        // n' = n if n is even, n+1 if n is odd. N = 2*n'.
59        let n_prime = n.checked_add(n % 2).ok_or_else(|| {
60            crate::rules::ReductionError::integer_overflow::<
61                MaxCut<SimpleGraph, i64>,
62                MinimumCutIntoBoundedSets<SimpleGraph, i64>,
63            >("padding the source vertex count")
64        })?;
65        let big_n = n_prime.checked_mul(2).ok_or_else(|| {
66            crate::rules::ReductionError::integer_overflow::<
67                MaxCut<SimpleGraph, i64>,
68                MinimumCutIntoBoundedSets<SimpleGraph, i64>,
69            >("computing the target vertex count")
70        })?;
71
72        // Step 2: Compute W_max
73        let w_max = self
74            .edge_weights()
75            .iter()
76            .copied()
77            .max()
78            .unwrap_or(0)
79            .checked_add(1)
80            .ok_or_else(|| {
81                crate::rules::ReductionError::integer_overflow::<
82                    MaxCut<SimpleGraph, i64>,
83                    MinimumCutIntoBoundedSets<SimpleGraph, i64>,
84                >("computing the inverted-weight ceiling")
85            })?;
86
87        // Build an adjacency lookup for the original graph
88        let orig_edges = self.graph().edges();
89        let mut edge_weight_map: std::collections::HashMap<(usize, usize), i64> =
90            std::collections::HashMap::new();
91        for (&(u, v), w) in orig_edges.iter().zip(self.edge_weights()) {
92            let (a, b) = if u < v { (u, v) } else { (v, u) };
93            edge_weight_map.insert((a, b), w);
94        }
95
96        // Step 3: Build complete graph K_N with inverted weights
97        let mut edges = Vec::new();
98        let mut weights = Vec::new();
99        for i in 0..big_n {
100            for j in (i + 1)..big_n {
101                edges.push((i, j));
102                if let Some(&w) = edge_weight_map.get(&(i, j)) {
103                    weights.push(w_max.checked_sub(w).ok_or_else(|| {
104                        crate::rules::ReductionError::integer_overflow::<
105                            MaxCut<SimpleGraph, i64>,
106                            MinimumCutIntoBoundedSets<SimpleGraph, i64>,
107                        >("inverting an edge weight")
108                    })?);
109                } else {
110                    weights.push(w_max);
111                }
112            }
113        }
114
115        // Step 4: Set source, sink, size_bound
116        let source_vertex = n_prime;
117        let sink_vertex = n_prime.checked_add(1).ok_or_else(|| {
118            crate::rules::ReductionError::integer_overflow::<
119                MaxCut<SimpleGraph, i64>,
120                MinimumCutIntoBoundedSets<SimpleGraph, i64>,
121            >("computing the target sink vertex")
122        })?;
123        let size_bound = n_prime;
124
125        let target = MinimumCutIntoBoundedSets::new(
126            SimpleGraph::new(big_n, edges),
127            weights,
128            source_vertex,
129            sink_vertex,
130            size_bound,
131        );
132
133        Ok(ReductionMaxCutToMinCutBounded {
134            target,
135            original_n: n,
136        })
137    }
138}
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
142    use crate::export::SolutionPair;
143    use crate::solvers::BruteForce;
144
145    vec![crate::example_db::specs::RuleExampleSpec {
146        id: "maxcut_to_minimumcutintoboundedsets",
147        build: || {
148            // Triangle with unit weights: max cut = 2
149            let source = MaxCut::new(
150                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
151                vec![1i64, 1, 1],
152            );
153            let reduction =
154                ReduceTo::<MinimumCutIntoBoundedSets<SimpleGraph, i64>>::reduce_to(&source)
155                    .expect("reduction should succeed");
156
157            // Find optimal source and target solutions
158            let solver = BruteForce::new();
159            let source_witness = solver
160                .solve(&source)
161                .expect("canonical source evaluation must succeed")
162                .expect("canonical source must have an optimum");
163            let target_witness = solver
164                .solve(reduction.target_problem())
165                .expect("canonical target evaluation must succeed")
166                .expect("canonical target must have an optimum");
167
168            crate::example_db::specs::assemble_rule_example(
169                &source,
170                reduction.target_problem(),
171                vec![SolutionPair {
172                    source_config: serde_json::json!(source_witness),
173                    target_config: serde_json::json!(target_witness),
174                }],
175            )
176        },
177    }]
178}
179
180#[cfg(test)]
181#[path = "../unit_tests/rules/maxcut_minimumcutintoboundedsets.rs"]
182mod tests;
problemreductions/rules/maxcut_minimumcutintoboundedsets.rs

problemreductions/rules/
maxcut_minimumcutintoboundedsets.rs
