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, i64>;
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(
52        &self,
53        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
54    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
55        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
56
57        Ok(target_solution.to_vec())
58    }
59}
60
61#[reduction(
62    transform = exact {
63        num_rows = "num_vertices",
64    }
65)]
66impl ReduceTo<MinimumMatrixCover> for MaxCut<SimpleGraph, i64> {
67    type Result = ReductionMaxCutToMMC;
68
69    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
70        let n = self.graph().num_vertices();
71        let mut matrix: Vec<Vec<i64>> = vec![vec![0i64; n]; n];
72
73        for (u, v, w) in self.edges() {
74            if w < 0 {
75                return Err(crate::rules::ReductionError::invalid_target::<
76                    MaxCut<SimpleGraph, i64>,
77                    MinimumMatrixCover,
78                >(format!(
79                    "edge ({u}, {v}) has negative weight {w}"
80                )));
81            }
82            let w64 = w;
83            matrix[u][v] = w64;
84            matrix[v][u] = w64;
85        }
86
87        Ok(ReductionMaxCutToMMC {
88            target: MinimumMatrixCover::new(matrix),
89        })
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    use crate::export::SolutionPair;
96
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "maxcut_to_minimummatrixcover",
99        build: || {
100            // Canonical example: C_4 (4-cycle) with unit weights.
101            // W = 4, max cut = 4 (partition {0,2} vs {1,3} cuts all edges).
102            // The target's minimum quadratic form value is 2W - 4 * cut = 8 - 16 = -8.
103            let source = MaxCut::<SimpleGraph, i64>::new(
104                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (0, 3)]),
105                vec![1, 1, 1, 1],
106            );
107            crate::example_db::specs::rule_example_with_witness::<_, MinimumMatrixCover>(
108                source,
109                SolutionPair {
110                    // S = {0, 2}: vertices 0 and 2 have f = +1.
111                    source_config: serde_json::json!(vec![true, false, true, false]),
112                    target_config: serde_json::json!(vec![true, false, true, false]),
113                },
114            )
115        },
116    }]
117}
118
119#[cfg(test)]
120#[path = "../unit_tests/rules/maxcut_minimummatrixcover.rs"]
121mod tests;
problemreductions/rules/maxcut_minimummatrixcover.rs

problemreductions/rules/
maxcut_minimummatrixcover.rs
