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::{BipartiteGraph, 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", "BipartiteGraph"]),
19        ],
20        category: crate::registry::ProblemCategory::Graph,
21        module_path: module_path!(),
22        description: "Find a minimum-size matching that cannot be extended",
23        fields: &[
24            FieldInfo { name: "graph", type_name: "G", description: "The underlying graph G=(V,E)" },
25        ],
26    }
27}
28
29/// The Minimum Maximal Matching problem.
30///
31/// Given a graph G = (V, E), find a matching M ⊆ E of minimum cardinality
32/// such that M is maximal: every edge not in M shares an endpoint with some
33/// edge in M (i.e., M cannot be extended by adding any further edge).
34///
35/// # Type Parameters
36///
37/// * `G` - The graph type (e.g., `SimpleGraph`)
38///
39/// # Example
40///
41/// ```
42/// use problemreductions::models::graph::MinimumMaximalMatching;
43/// use problemreductions::topology::SimpleGraph;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// // Path graph P4: 0-1-2-3
47/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
48/// let problem = MinimumMaximalMatching::new(graph);
49///
50/// let solver = BruteForce::new();
51/// let solution = solver.solve(&problem).unwrap().unwrap();
52///
53/// // Minimum maximal matching has 1 edge (e.g., edge (1,2))
54/// let count = solution.iter().filter(|&&selected| selected).count();
55/// assert_eq!(count, 1);
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58pub struct MinimumMaximalMatching<G> {
59    /// The underlying graph.
60    graph: G,
61}
62
63impl<G: Graph> MinimumMaximalMatching<G> {
64    /// Create a MinimumMaximalMatching problem from a graph.
65    pub fn new(graph: G) -> Self {
66        Self { graph }
67    }
68
69    /// Get a reference to the underlying graph.
70    pub fn graph(&self) -> &G {
71        &self.graph
72    }
73
74    /// Get the number of vertices in the underlying graph.
75    pub fn num_vertices(&self) -> usize {
76        self.graph.num_vertices()
77    }
78
79    /// Get the number of edges in the underlying graph.
80    pub fn num_edges(&self) -> usize {
81        self.graph.num_edges()
82    }
83
84    /// Check whether a configuration is a valid maximal matching.
85    ///
86    /// Returns `true` iff:
87    /// 1. The selected edges form a matching (no two share an endpoint).
88    /// 2. The matching is maximal (every non-selected edge shares an endpoint
89    ///    with some selected edge).
90    pub fn is_valid_maximal_matching(&self, config: &[bool]) -> bool {
91        let edges = self.graph.edges();
92        let n = self.graph.num_vertices();
93
94        // Step 1: Check matching property.
95        let mut vertex_used = vec![false; n];
96        for (idx, &sel) in config.iter().enumerate() {
97            if sel {
98                let (u, v) = edges[idx];
99                if vertex_used[u] || vertex_used[v] {
100                    return false;
101                }
102                vertex_used[u] = true;
103                vertex_used[v] = true;
104            }
105        }
106
107        // Step 2: Check maximality — every unselected edge must be blocked.
108        for (idx, &sel) in config.iter().enumerate() {
109            if !sel {
110                let (u, v) = edges[idx];
111                // Edge (u,v) is blocked iff u or v is already matched.
112                if !vertex_used[u] && !vertex_used[v] {
113                    return false;
114                }
115            }
116        }
117
118        true
119    }
120}
121
122impl<G> Problem for MinimumMaximalMatching<G>
123where
124    G: Graph + crate::variant::VariantParam,
125{
126    const NAME: &'static str = "MinimumMaximalMatching";
127    type Solution = Vec<bool>;
128    type Value = Min<i64>;
129
130    crate::problem_parameters![("num_edges", num_edges), ("num_vertices", num_vertices),];
131
132    fn variant() -> Vec<(&'static str, &'static str)> {
133        crate::variant_params![G]
134    }
135
136    fn evaluate(
137        &self,
138        config: &Self::Solution,
139    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
140        Ok({
141            if config.len() != self.graph.num_edges() {
142                return Err(crate::traits::EvaluationError::InvalidConfiguration(
143                    "edge-selection length does not match the graph".into(),
144                ));
145            }
146            if !self.is_valid_maximal_matching(config) {
147                return Ok(Min(None));
148            }
149            let count = config.iter().filter(|&&selected| selected).count();
150            Min(Some(i64::try_from(count).map_err(|_| {
151                crate::traits::EvaluationError::IntegerOverflow(
152                    "converting matching cardinality to i64".into(),
153                )
154            })?))
155        })
156    }
157}
158
159impl<G> crate::solvers::BruteForceProblem for MinimumMaximalMatching<G>
160where
161    G: Graph + crate::variant::VariantParam,
162{
163    fn dimensions(&self) -> Vec<usize> {
164        vec![2; self.graph.num_edges()]
165    }
166}
167
168crate::impl_random_generate!(
169    MinimumMaximalMatching<SimpleGraph>,
170    crate::random::SimpleGraphRandomSpec,
171    |spec| { Ok(MinimumMaximalMatching::new(spec.graph()?)) }
172);
173
174crate::declare_variants! {
175    default MinimumMaximalMatching<SimpleGraph> => "1.3160^num_vertices" random,
176    MinimumMaximalMatching<BipartiteGraph> => "1.3160^num_vertices",
177}
178
179crate::register_brute_force! {
180    MinimumMaximalMatching<SimpleGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
181    MinimumMaximalMatching<BipartiteGraph> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
182}
183
184#[cfg(feature = "example-db")]
185pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
186    // Path graph P6: 6 vertices, edges [(0,1),(1,2),(2,3),(3,4),(4,5)]
187    // config [0,1,0,1,0] = edges {(1,2),(3,4)} — a maximal matching of size 2.
188    vec![crate::example_db::specs::ModelExampleSpec {
189        id: "minimum_maximal_matching_simplegraph",
190        instance: Box::new(MinimumMaximalMatching::new(SimpleGraph::new(
191            6,
192            vec![(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
193        ))),
194        optimal_config: serde_json::json!(vec![false, true, false, true, false]),
195        optimal_value: serde_json::json!(2),
196    }]
197}
198
199#[cfg(test)]
200#[path = "../../unit_tests/models/graph/minimum_maximal_matching.rs"]
201mod tests;
problemreductions/models/graph/minimum_maximal_matching.rs

problemreductions/models/graph/
minimum_maximal_matching.rs
