problemreductions/rules/
maxcut_minimummatrixcover.rs

1//! Reduction from MaxCut to MinimumMatrixCover.
2//!
3//! Given a MaxCut instance `(G, w)` with nonnegative integer edge weights,
4//! the target matrix `A` is the symmetric weighted adjacency matrix of `G`:
5//!     `a_{ij} = w({i, j})` if `{i, j} ∈ E`, otherwise `0` (diagonal is `0`).
6//!
7//! The key identity is
8//!     `Σ_{i,j} a_{ij} · f(i) · f(j) = 2 W − 4 · cut(S)`,
9//! where `S = { i : f(i) = +1 }` and `W = Σ_{e ∈ E} w(e)`. Minimizing the
10//! quadratic form is therefore equivalent to maximizing the cut, and the
11//! reduction is witness-preserving via the identity map between MaxCut's
12//! partition encoding (`config[i] = 1 ⇔ i ∈ S`) and MinimumMatrixCover's
13//! sign encoding (`config[i] = 1 ⇔ f(i) = +1 ⇔ i ∈ S`).
14//!
15//! **Precondition:** all edge weights must be nonnegative. The reduction
16//! panics on any negative weight, since `MinimumMatrixCover` requires a
17//! nonnegative integer matrix. Negative-weight `MaxCut` instances are out
18//! of scope and must use a different (preprocessing) reduction.
19//!
20//! Reference: Garey & Johnson, *Computers and Intractability* (1979),
21//! Appendix A1.2, MS13 ("Transformation from MAXIMUM CUT").
22
23use crate::models::algebraic::MinimumMatrixCover;
24use crate::models::graph::MaxCut;
25use crate::reduction;
26use crate::rules::traits::{ReduceTo, ReductionResult};
27use crate::topology::{Graph, SimpleGraph};
28
29/// Result of reducing MaxCut to MinimumMatrixCover.
30#[derive(Debug, Clone)]
31pub struct ReductionMaxCutToMMC {
32    target: MinimumMatrixCover,
33}
34
35impl ReductionResult for ReductionMaxCutToMMC {
36    type Source = MaxCut<SimpleGraph, i32>;
37    type Target = MinimumMatrixCover;
38
39    fn target_problem(&self) -> &Self::Target {
40        &self.target
41    }
42
43    /// Solution extraction is the identity.
44    ///
45    /// Both encodings agree that bit `i = 1` means vertex `i` is in `S`:
46    /// MaxCut treats `config[i] = 1` as one side of the partition, and
47    /// MinimumMatrixCover treats `config[i] = 1` as `f(i) = +1`, i.e.,
48    /// vertex `i` in `S`. The complementary assignment is equally optimal
49    /// because the quadratic form (and the cut) is invariant under
50    /// `f -> -f`.
51    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
52        target_solution.to_vec()
53    }
54}
55
56#[reduction(
57    overhead = {
58        num_rows = "num_vertices",
59    }
60)]
61impl ReduceTo<MinimumMatrixCover> for MaxCut<SimpleGraph, i32> {
62    type Result = ReductionMaxCutToMMC;
63
64    fn reduce_to(&self) -> Self::Result {
65        let n = self.graph().num_vertices();
66        let mut matrix: Vec<Vec<i64>> = vec![vec![0i64; n]; n];
67
68        for (u, v, w) in self.edges() {
69            assert!(
70                w >= 0,
71                "MaxCut -> MinimumMatrixCover requires nonnegative edge weights, got w({u},{v}) = {w}"
72            );
73            let w64 = w as i64;
74            matrix[u][v] = w64;
75            matrix[v][u] = w64;
76        }
77
78        ReductionMaxCutToMMC {
79            target: MinimumMatrixCover::new(matrix),
80        }
81    }
82}
83
84#[cfg(feature = "example-db")]
85pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
86    use crate::export::SolutionPair;
87
88    vec![crate::example_db::specs::RuleExampleSpec {
89        id: "maxcut_to_minimummatrixcover",
90        build: || {
91            // Canonical example: C_4 (4-cycle) with unit weights.
92            // W = 4, max cut = 4 (partition {0,2} vs {1,3} cuts all edges).
93            // The target's minimum quadratic form value is 2W - 4 * cut = 8 - 16 = -8.
94            let source = MaxCut::<SimpleGraph, i32>::new(
95                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (0, 3)]),
96                vec![1, 1, 1, 1],
97            );
98            crate::example_db::specs::rule_example_with_witness::<_, MinimumMatrixCover>(
99                source,
100                SolutionPair {
101                    // S = {0, 2}: vertices 0 and 2 have f = +1.
102                    source_config: vec![1, 0, 1, 0],
103                    target_config: vec![1, 0, 1, 0],
104                },
105            )
106        },
107    }]
108}
109
110#[cfg(test)]
111#[path = "../unit_tests/rules/maxcut_minimummatrixcover.rs"]
112mod tests;
problemreductions/rules/maxcut_minimummatrixcover.rs

problemreductions/rules/
maxcut_minimummatrixcover.rs
