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#[reduction(
44    transform = exact {
45        num_vertices = "2 * num_vertices + 2",
46        num_edges = "(num_vertices + 1) * (2 * num_vertices + 1)",
47    }
48)]
49impl ReduceTo<MinimumCutIntoBoundedSets<SimpleGraph, i64>> for MaxCut<SimpleGraph, i64> {
50    type Result = ReductionMaxCutToMinCutBounded;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let n = self.graph().num_vertices();
54
55        // Step 1: Pad to even vertex count.
56        // n' = n if n is even, n+1 if n is odd. N = 2*n'.
57        let n_prime = n.checked_add(n % 2).ok_or_else(|| {
58            crate::rules::ReductionError::integer_overflow::<
59                MaxCut<SimpleGraph, i64>,
60                MinimumCutIntoBoundedSets<SimpleGraph, i64>,
61            >("padding the source vertex count")
62        })?;
63        let big_n = n_prime.checked_mul(2).ok_or_else(|| {
64            crate::rules::ReductionError::integer_overflow::<
65                MaxCut<SimpleGraph, i64>,
66                MinimumCutIntoBoundedSets<SimpleGraph, i64>,
67            >("computing the target vertex count")
68        })?;
69
70        // Step 2: Compute W_max
71        let w_max = self
72            .edge_weights()
73            .iter()
74            .copied()
75            .max()
76            .unwrap_or(0)
77            .checked_add(1)
78            .ok_or_else(|| {
79                crate::rules::ReductionError::integer_overflow::<
80                    MaxCut<SimpleGraph, i64>,
81                    MinimumCutIntoBoundedSets<SimpleGraph, i64>,
82                >("computing the inverted-weight ceiling")
83            })?;
84
85        // Build an adjacency lookup for the original graph
86        let orig_edges = self.graph().edges();
87        let mut edge_weight_map: std::collections::HashMap<(usize, usize), i64> =
88            std::collections::HashMap::new();
89        for (&(u, v), w) in orig_edges.iter().zip(self.edge_weights()) {
90            let (a, b) = if u < v { (u, v) } else { (v, u) };
91            edge_weight_map.insert((a, b), w);
92        }
93
94        // Step 3: Build complete graph K_N with inverted weights
95        let mut edges = Vec::new();
96        let mut weights = Vec::new();
97        for i in 0..big_n {
98            for j in (i + 1)..big_n {
99                edges.push((i, j));
100                if let Some(&w) = edge_weight_map.get(&(i, j)) {
101                    weights.push(w_max.checked_sub(w).ok_or_else(|| {
102                        crate::rules::ReductionError::integer_overflow::<
103                            MaxCut<SimpleGraph, i64>,
104                            MinimumCutIntoBoundedSets<SimpleGraph, i64>,
105                        >("inverting an edge weight")
106                    })?);
107                } else {
108                    weights.push(w_max);
109                }
110            }
111        }
112
113        // Step 4: Set source, sink, size_bound
114        let source_vertex = n_prime;
115        let sink_vertex = n_prime.checked_add(1).ok_or_else(|| {
116            crate::rules::ReductionError::integer_overflow::<
117                MaxCut<SimpleGraph, i64>,
118                MinimumCutIntoBoundedSets<SimpleGraph, i64>,
119            >("computing the target sink vertex")
120        })?;
121        let size_bound = n_prime;
122
123        let target = MinimumCutIntoBoundedSets::new(
124            SimpleGraph::new(big_n, edges),
125            weights,
126            source_vertex,
127            sink_vertex,
128            size_bound,
129        );
130
131        Ok(ReductionMaxCutToMinCutBounded {
132            target,
133            original_n: n,
134        })
135    }
136}
137
138#[cfg(feature = "example-db")]
139pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
140    use crate::export::SolutionPair;
141    use crate::solvers::BruteForce;
142
143    vec![crate::example_db::specs::RuleExampleSpec {
144        id: "maxcut_to_minimumcutintoboundedsets",
145        build: || {
146            // Triangle with unit weights: max cut = 2
147            let source = MaxCut::new(
148                SimpleGraph::new(3, vec![(0, 1), (1, 2), (0, 2)]),
149                vec![1i64, 1, 1],
150            );
151            let reduction =
152                ReduceTo::<MinimumCutIntoBoundedSets<SimpleGraph, i64>>::reduce_to(&source)
153                    .expect("reduction should succeed");
154
155            // Find optimal source and target solutions
156            let solver = BruteForce::new();
157            let source_witness = solver
158                .solve(&source)
159                .expect("canonical source evaluation must succeed")
160                .expect("canonical source must have an optimum");
161            let target_witness = solver
162                .solve(reduction.target_problem())
163                .expect("canonical target evaluation must succeed")
164                .expect("canonical target must have an optimum");
165
166            crate::example_db::specs::assemble_rule_example(
167                &source,
168                reduction.target_problem(),
169                vec![SolutionPair {
170                    source_config: serde_json::json!(source_witness),
171                    target_config: serde_json::json!(target_witness),
172                }],
173            )
174        },
175    }]
176}
177
178#[cfg(test)]
179#[path = "../unit_tests/rules/maxcut_minimumcutintoboundedsets.rs"]
180mod tests;
problemreductions/rules/maxcut_minimumcutintoboundedsets.rs

problemreductions/rules/
maxcut_minimumcutintoboundedsets.rs
