problemreductions/rules/
minimummaximalmatching_ilp.rs

1//! Reduction from MinimumMaximalMatching to ILP (Integer Linear Programming).
2//!
3//! The Minimum Maximal Matching problem can be formulated as a binary ILP:
4//! - Variables: One binary variable e_i per edge (0 = not selected, 1 = selected)
5//! - Matching constraints: For each vertex v, sum of e_i for edges incident to v <= 1
6//! - Maximality constraints: For each edge j, e_j + sum_{i shares endpoint with j, i≠j} e_i >= 1
7//!   (if edge j is not selected, at least one edge adjacent to it must be)
8//! - Objective: Minimize sum e_i
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::MinimumMaximalMatching;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::{Graph, SimpleGraph};
15
16/// Result of reducing MinimumMaximalMatching to ILP.
17///
18/// This reduction creates a binary ILP where:
19/// - Each edge corresponds to a binary variable
20/// - Vertex constraints ensure at most one incident edge is selected per vertex
21/// - Edge constraints ensure that each edge is either selected or blocked by an adjacent
22///   selected edge (maximality)
23/// - The objective minimizes the total number of selected edges
24#[derive(Debug, Clone)]
25pub struct ReductionMMMToILP {
26    target: ILP<bool>,
27}
28
29impl ReductionResult for ReductionMMMToILP {
30    type Source = MinimumMaximalMatching<SimpleGraph>;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    /// Extract solution from ILP back to MinimumMaximalMatching.
38    ///
39    /// Since the mapping is 1:1 (each edge maps to one binary variable),
40    /// the solution extraction is simply copying the configuration.
41    fn extract_solution(
42        &self,
43        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
44    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
45        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
46
47        Ok(target_solution.iter().map(|&value| value == 1).collect())
48    }
49}
50
51// At most n nonempty incidence rows and exactly m maximality rows. Incidence
52// contributes at most 2m coefficients; each maximality row lists at most m
53// distinct edge variables. Normalizing loop incidences can only lower the count.
54#[reduction(transform = {
55    exact {
56        num_vars = "num_edges",
57    },
58    upper_bound {
59        max_constraint_magnitude_bits = "2",
60        num_constraints = "num_vertices + num_edges",
61        num_nonzeros = "2 * num_edges + num_edges^2",
62    },
63})]
64impl ReduceTo<ILP<bool>> for MinimumMaximalMatching<SimpleGraph> {
65    type Result = ReductionMMMToILP;
66
67    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
68        let edges = self.graph().edges();
69        let num_vars = edges.len();
70        let mut constraints = Vec::new();
71
72        // Matching constraints: for each vertex v, sum of incident edge variables <= 1.
73        // Build vertex -> incident edge index map.
74        let n = self.graph().num_vertices();
75        let mut v2e: Vec<Vec<usize>> = vec![Vec::new(); n];
76        for (idx, &(u, v)) in edges.iter().enumerate() {
77            v2e[u].push(idx);
78            v2e[v].push(idx);
79        }
80        for incident in &v2e {
81            if !incident.is_empty() {
82                let terms: Vec<(usize, i64)> = incident.iter().map(|&e| (e, 1)).collect();
83                constraints.push(LinearConstraint::le(terms, 1));
84            }
85        }
86
87        // Maximality constraints: for each edge j, the closed neighborhood (j itself plus all
88        // edges sharing an endpoint with j) must contain at least one selected edge.
89        // i.e. e_j + sum_{i: i shares endpoint with j, i≠j} e_i >= 1  for all j.
90        for (j, &(uj, vj)) in edges.iter().enumerate() {
91            // Collect all edges in the closed neighborhood of edge j.
92            let mut neighbors: Vec<usize> = vec![j];
93            for &i in v2e[uj].iter().chain(v2e[vj].iter()) {
94                if i != j && !neighbors.contains(&i) {
95                    neighbors.push(i);
96                }
97            }
98            let terms: Vec<(usize, i64)> = neighbors.iter().map(|&i| (i, 1)).collect();
99            constraints.push(LinearConstraint::ge(terms, 1));
100        }
101
102        // Objective: minimize sum e_i
103        let objective: Vec<(usize, i64)> = (0..num_vars).map(|i| (i, 1)).collect();
104
105        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
106            .map_err(Self::target_construction)?;
107        Ok(ReductionMMMToILP { target })
108    }
109}
110
111#[cfg(feature = "example-db")]
112pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
113    vec![crate::example_db::specs::RuleExampleSpec {
114        id: "minimummaximalmatching_to_ilp",
115        build: || {
116            // Path graph P6
117            let source = MinimumMaximalMatching::new(SimpleGraph::new(
118                6,
119                vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
120            ));
121            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
122        },
123    }]
124}
125
126#[cfg(test)]
127#[path = "../unit_tests/rules/minimummaximalmatching_ilp.rs"]
128mod tests;
problemreductions/rules/minimummaximalmatching_ilp.rs

problemreductions/rules/
minimummaximalmatching_ilp.rs
