problemreductions/models/graph/
minimum_maximal_matching.rs

1//! MinimumMaximalMatching problem implementation.
2//!
3//! The Minimum Maximal Matching problem asks for a matching of minimum size
4//! that is maximal (cannot be extended by adding any edge).
5
6use crate::registry::{FieldInfo, ProblemSchemaEntry, VariantDimension};
7use crate::topology::{Graph, SimpleGraph};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "MinimumMaximalMatching",
15        display_name: "Minimum Maximal Matching",
16        aliases: &[],
17        dimensions: &[
18            VariantDimension::new("graph", "SimpleGraph", &["SimpleGraph"]),
19        ],
20        module_path: module_path!(),
21        description: "Find a minimum-size matching that cannot be extended",
22        fields: &[
23            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
24        ],
25    }
26}
27
28/// The Minimum Maximal Matching problem.
29///
30/// Given a graph G = (V, E), find a matching M ⊆ E of minimum cardinality
31/// such that M is maximal: every edge not in M shares an endpoint with some
32/// edge in M (i.e., M cannot be extended by adding any further edge).
33///
34/// # Type Parameters
35///
36/// * `G` - The graph type (e.g., `SimpleGraph`)
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::graph::MinimumMaximalMatching;
42/// use problemreductions::topology::SimpleGraph;
43/// use problemreductions::{Problem, Solver, BruteForce};
44///
45/// // Path graph P4: 0-1-2-3
46/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
47/// let problem = MinimumMaximalMatching::new(graph);
48///
49/// let solver = BruteForce::new();
50/// let solution = solver.find_witness(&problem).unwrap();
51///
52/// // Minimum maximal matching has 1 edge (e.g., edge (1,2))
53/// let count: usize = solution.iter().sum();
54/// assert_eq!(count, 1);
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MinimumMaximalMatching<G> {
58    /// The underlying graph.
59    graph: G,
60}
61
62impl<G: Graph> MinimumMaximalMatching<G> {
63    /// Create a MinimumMaximalMatching problem from a graph.
64    pub fn new(graph: G) -> Self {
65        Self { graph }
66    }
67
68    /// Get a reference to the underlying graph.
69    pub fn graph(&self) -> &G {
70        &self.graph
71    }
72
73    /// Get the number of vertices in the underlying graph.
74    pub fn num_vertices(&self) -> usize {
75        self.graph.num_vertices()
76    }
77
78    /// Get the number of edges in the underlying graph.
79    pub fn num_edges(&self) -> usize {
80        self.graph.num_edges()
81    }
82
83    /// Check whether a configuration is a valid maximal matching.
84    ///
85    /// Returns `true` iff:
86    /// 1. The selected edges form a matching (no two share an endpoint).
87    /// 2. The matching is maximal (every non-selected edge shares an endpoint
88    ///    with some selected edge).
89    pub fn is_valid_maximal_matching(&self, config: &[usize]) -> bool {
90        let edges = self.graph.edges();
91        let n = self.graph.num_vertices();
92
93        // Step 1: Check matching property.
94        let mut vertex_used = vec![false; n];
95        for (idx, &sel) in config.iter().enumerate() {
96            if sel == 1 {
97                let (u, v) = edges[idx];
98                if vertex_used[u] || vertex_used[v] {
99                    return false;
100                }
101                vertex_used[u] = true;
102                vertex_used[v] = true;
103            }
104        }
105
106        // Step 2: Check maximality — every unselected edge must be blocked.
107        for (idx, &sel) in config.iter().enumerate() {
108            if sel == 0 {
109                let (u, v) = edges[idx];
110                // Edge (u,v) is blocked iff u or v is already matched.
111                if !vertex_used[u] && !vertex_used[v] {
112                    return false;
113                }
114            }
115        }
116
117        true
118    }
119}
120
121impl<G> Problem for MinimumMaximalMatching<G>
122where
123    G: Graph + crate::variant::VariantParam,
124{
125    const NAME: &'static str = "MinimumMaximalMatching";
126    type Value = Min<usize>;
127
128    fn variant() -> Vec<(&'static str, &'static str)> {
129        crate::variant_params![G]
130    }
131
132    fn dims(&self) -> Vec<usize> {
133        vec![2; self.graph.num_edges()]
134    }
135
136    fn evaluate(&self, config: &[usize]) -> Min<usize> {
137        if config.len() != self.graph.num_edges() {
138            return Min(None);
139        }
140        if !self.is_valid_maximal_matching(config) {
141            return Min(None);
142        }
143        let count = config.iter().filter(|&&x| x == 1).count();
144        Min(Some(count))
145    }
146}
147
148crate::declare_variants! {
149    default MinimumMaximalMatching<SimpleGraph> => "1.3160^num_vertices",
150}
151
152#[cfg(feature = "example-db")]
153pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
154    // Path graph P6: 6 vertices, edges [(0,1),(1,2),(2,3),(3,4),(4,5)]
155    // config [0,1,0,1,0] = edges {(1,2),(3,4)} — a maximal matching of size 2.
156    vec![crate::example_db::specs::ModelExampleSpec {
157        id: "minimum_maximal_matching_simplegraph",
158        instance: Box::new(MinimumMaximalMatching::new(SimpleGraph::new(
159            6,
160            vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
161        ))),
162        optimal_config: vec![0, 1, 0, 1, 0],
163        optimal_value: serde_json::json!(2),
164    }]
165}
166
167#[cfg(test)]
168#[path = "../../unit_tests/models/graph/minimum_maximal_matching.rs"]
169mod tests;
problemreductions/models/graph/minimum_maximal_matching.rs

problemreductions/models/graph/
minimum_maximal_matching.rs
