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#[reduction(
52    transform = exact {
53        num_vars = "num_edges",
54        num_constraints = "num_vertices + num_edges",
55    },
56    unavailable = {
57        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
58    }
59)]
60impl ReduceTo<ILP<bool>> for MinimumMaximalMatching<SimpleGraph> {
61    type Result = ReductionMMMToILP;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        let edges = self.graph().edges();
65        let num_vars = edges.len();
66        let mut constraints = Vec::new();
67
68        // Matching constraints: for each vertex v, sum of incident edge variables <= 1.
69        // Build vertex -> incident edge index map.
70        let n = self.graph().num_vertices();
71        let mut v2e: Vec<Vec<usize>> = vec![Vec::new(); n];
72        for (idx, &(u, v)) in edges.iter().enumerate() {
73            v2e[u].push(idx);
74            v2e[v].push(idx);
75        }
76        for incident in &v2e {
77            if !incident.is_empty() {
78                let terms: Vec<(usize, i64)> = incident.iter().map(|&e| (e, 1)).collect();
79                constraints.push(LinearConstraint::le(terms, 1));
80            }
81        }
82
83        // Maximality constraints: for each edge j, the closed neighborhood (j itself plus all
84        // edges sharing an endpoint with j) must contain at least one selected edge.
85        // i.e. e_j + sum_{i: i shares endpoint with j, i≠j} e_i >= 1  for all j.
86        for (j, &(uj, vj)) in edges.iter().enumerate() {
87            // Collect all edges in the closed neighborhood of edge j.
88            let mut neighbors: Vec<usize> = vec![j];
89            for &i in v2e[uj].iter().chain(v2e[vj].iter()) {
90                if i != j && !neighbors.contains(&i) {
91                    neighbors.push(i);
92                }
93            }
94            let terms: Vec<(usize, i64)> = neighbors.iter().map(|&i| (i, 1)).collect();
95            constraints.push(LinearConstraint::ge(terms, 1));
96        }
97
98        // Objective: minimize sum e_i
99        let objective: Vec<(usize, i64)> = (0..num_vars).map(|i| (i, 1)).collect();
100
101        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
102            .map_err(Self::target_construction)?;
103        Ok(ReductionMMMToILP { target })
104    }
105}
106
107#[cfg(feature = "example-db")]
108pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
109    vec![crate::example_db::specs::RuleExampleSpec {
110        id: "minimummaximalmatching_to_ilp",
111        build: || {
112            // Path graph P6
113            let source = MinimumMaximalMatching::new(SimpleGraph::new(
114                6,
115                vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
116            ));
117            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/minimummaximalmatching_ilp.rs"]
124mod tests;
problemreductions/rules/minimummaximalmatching_ilp.rs

problemreductions/rules/
minimummaximalmatching_ilp.rs
