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, i32>,
19    /// Number of original vertices in the source problem.
20    original_n: usize,
21}
22
23impl ReductionResult for ReductionMaxCutToMinCutBounded {
24    type Source = MaxCut<SimpleGraph, i32>;
25    type Target = MinimumCutIntoBoundedSets<SimpleGraph, i32>;
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(&self, target_solution: &[usize]) -> Vec<usize> {
34        target_solution[..self.original_n].to_vec()
35    }
36}
37
38#[reduction(
39    overhead = {
40        num_vertices = "2 * num_vertices + 2",
41        num_edges = "(num_vertices + 1) * (2 * num_vertices + 1)",
42    }
43)]
44impl ReduceTo<MinimumCutIntoBoundedSets<SimpleGraph, i32>> for MaxCut<SimpleGraph, i32> {
45    type Result = ReductionMaxCutToMinCutBounded;
46
47    fn reduce_to(&self) -> Self::Result {
48        let n = self.graph().num_vertices();
49
50        // Step 1: Pad to even vertex count.
51        // n' = n if n is even, n+1 if n is odd. N = 2*n'.
52        let n_prime = n + (n % 2); // round up to even
53        let big_n = 2 * n_prime;
54
55        // Step 2: Compute W_max
56        let w_max = self.edge_weights().iter().copied().max().unwrap_or(0) + 1;
57
58        // Build an adjacency lookup for the original graph
59        let orig_edges = self.graph().edges();
60        let mut edge_weight_map: std::collections::HashMap<(usize, usize), i32> =
61            std::collections::HashMap::new();
62        for (idx, &(u, v)) in orig_edges.iter().enumerate() {
63            let w = *self.edge_weight_by_index(idx).unwrap();
64            let (a, b) = if u < v { (u, v) } else { (v, u) };
65            edge_weight_map.insert((a, b), w);
66        }
67
68        // Step 3: Build complete graph K_N with inverted weights
69        let mut edges = Vec::new();
70        let mut weights = Vec::new();
71        for i in 0..big_n {
72            for j in (i + 1)..big_n {
73                edges.push((i, j));
74                if let Some(&w) = edge_weight_map.get(&(i, j)) {
75                    weights.push(w_max - w);
76                } else {
77                    weights.push(w_max);
78                }
79            }
80        }
81
82        // Step 4: Set source, sink, size_bound
83        let source_vertex = n_prime;
84        let sink_vertex = n_prime + 1;
85        let size_bound = n_prime;
86
87        let target = MinimumCutIntoBoundedSets::new(
88            SimpleGraph::new(big_n, edges),
89            weights,
90            source_vertex,
91            sink_vertex,
92            size_bound,
93        );
94
95        ReductionMaxCutToMinCutBounded {
96            target,
97            original_n: n,
98        }
99    }
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    use crate::export::SolutionPair;
105    use crate::solvers::BruteForce;
106
107    vec![crate::example_db::specs::RuleExampleSpec {
108        id: "maxcut_to_minimumcutintoboundedsets",
109        build: || {
110            // Triangle with unit weights: max cut = 2
111            let source = MaxCut::new(
112                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
113                vec![1i32, 1, 1],
114            );
115            let reduction =
116                ReduceTo::<MinimumCutIntoBoundedSets<SimpleGraph, i32>>::reduce_to(&source);
117
118            // Find optimal source and target solutions
119            let solver = BruteForce::new();
120            let source_witness = solver.find_witness(&source).unwrap();
121            let target_witness = solver.find_witness(reduction.target_problem()).unwrap();
122
123            crate::example_db::specs::assemble_rule_example(
124                &source,
125                reduction.target_problem(),
126                vec![SolutionPair {
127                    source_config: source_witness,
128                    target_config: target_witness,
129                }],
130            )
131        },
132    }]
133}
134
135#[cfg(test)]
136#[path = "../unit_tests/rules/maxcut_minimumcutintoboundedsets.rs"]
137mod tests;
problemreductions/rules/maxcut_minimumcutintoboundedsets.rs

problemreductions/rules/
maxcut_minimumcutintoboundedsets.rs
