[Model] MinimumMaximalMatching

[isPANN]

Motivation

MINIMUM MAXIMAL MATCHING (P21) from Garey & Johnson, A1.1 GT10. A classical NP-complete graph problem equivalent to Minimum Edge Dominating Set — the optimal values coincide (Yannakakis & Gavril, 1978). Useful as a reduction target from Vertex Cover (the original NP-completeness proof is by transformation from Vertex Cover for cubic graphs). Remains NP-complete for planar graphs and bipartite graphs with maximum degree 3.

Definition

Name: MinimumMaximalMatching
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT10

Mathematical definition:

Given a graph G = (V, E), find a maximal matching of minimum cardinality. A matching is a subset E' ⊆ E such that no two edges in E' share a common endpoint. A matching E' is maximal if every edge in E \ E' shares at least one endpoint with some edge in E'. The objective is to minimize |E'| over all maximal matchings.

Variables

• Count: |E| (one per edge)
• Per-variable domain: {0, 1}
• Meaning: Whether each edge is included in the matching (1) or not (0). The objective minimizes the number of selected edges subject to the matching being maximal.

Schema (data type)

Type name: MinimumMaximalMatching
Variants: graph: SimpleGraph

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)

Complexity

• Best known exact algorithm: 1.3160^num_vertices by Xiao and Nagamochi (2014), "A Refined Exact Algorithm for Edge Dominating Set", Theoretical Computer Science 560, pp. 207–216. The minimum maximal matching problem is equivalent to the minimum edge dominating set problem (the size of a minimum edge dominating set equals the size of a minimum maximal matching). The algorithm uses branch-and-reduce with measure-and-conquer analysis, exploiting clique-producing vertices and cycle structures.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |E|.
QUESTION: Is there a subset E' ⊆ E with |E'| ≤ K such that E' is a maximal matching, i.e., no two edges in E' share a common endpoint and every edge in E−E' shares a common endpoint with some edge in E'?
Reference: [Yannakakis and Gavril, 1978]. Transformation from VERTEX COVER for cubic graphs.
Comment: Remains NP-complete for planar graphs and for bipartite graphs, in both cases even if no vertex degree exceeds 3. The problem of finding a maximum "maximal matching" is just the usual graph matching problem and is solvable in polynomial time (e.g., see [Lawler, 1976a]).

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other:

Reduction Rule Crossref

The direct MinimumMaximalMatching → ILP rule will be implemented together with this model (per project convention for models with direct ILP solvability).

Example Instance

Consider the path graph on 6 vertices: v0 — v1 — v2 — v3 — v4 — v5, with edges E = {(v0,v1), (v1,v2), (v2,v3), (v3,v4), (v4,v5)}.

All maximal matchings of this graph:

• {(v0,v1), (v2,v3), (v4,v5)} — size 3
• {(v0,v1), (v3,v4)} — size 2
• {(v1,v2), (v3,v4)} — size 2
• {(v1,v2), (v4,v5)} — size 2

For example, E' = {(v1,v2), (v3,v4)} is a maximal matching of size 2: no two edges share an endpoint, and every other edge is adjacent to some edge in E' — (v0,v1) shares v1 with (v1,v2), (v2,v3) shares v2 with (v1,v2) and v3 with (v3,v4), and (v4,v5) shares v4 with (v3,v4).

A single edge like {(v2,v3)} is NOT a maximal matching because (v0,v1) shares no endpoint with it, so it could still be added.

Expected Outcome

Optimal value: Min(2)
Optimal solution: E' = {(v1,v2), (v3,v4)} (or equivalently {(v0,v1), (v3,v4)} or {(v1,v2), (v4,v5)})
Suboptimal feasible solution: {(v0,v1), (v2,v3), (v4,v5)} with value 3 — this is maximal but not minimum.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	ILP solving claimed but no companion [Rule] issue linked
Non-trivial	✅ Pass	Distinct from MaximumMatching (polynomial) and all existing problems
Correctness	✅ Pass	Xiao & Nagamochi (2014) verified; O*(1.3160^n) confirmed
Well-written	❌ Fail	Decision/optimization mismatch, missing sections, example issues

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Novel problem: MinimumMaximalMatching does not exist in the codebase. ✅

Planned reductions: The "How to solve" section checks ILP, implying a planned reduction to ILP. However, no Reduction Rule Crossref section is present. Per template requirements, when direct ILP solving is claimed, the issue must link a companion [Rule] MinimumMaximalMatching to ILP issue (or explicitly state the ILP rule will be implemented together). → Fail

Motivation: "A classical NP-complete problem useful for reductions" is vague — it doesn't explain why this problem matters for the reduction graph or what concrete reductions it enables. Consider mentioning the equivalence to Minimum Edge Dominating Set and any planned reductions to/from existing problems.

Non-trivial

Pass. MinimumMaximalMatching is genuinely distinct from all existing problems:

• MaximumMatching finds the largest matching (polynomial, O(n³)) — fundamentally different objective
• MaximalIS (maximal independent set) operates on vertices, not edges
• No existing problem has the "minimum cardinality maximal matching" feasibility constraint

The NP-completeness is well-established (Yannakakis & Gavril 1978, per G&J).

Correctness

References verified:

• Garey & Johnson A1.1 GT10: Correct — this is indeed the Minimum Maximal Matching problem. ✅
• Xiao & Nagamochi (2014): Paper confirmed — "A Refined Exact Algorithm for Edge Dominating Set", Theoretical Computer Science 560, pp. 207–216. The O*(1.3160^n) bound is correct. ✅
• Equivalence to Minimum Edge Dominating Set: Correct — a minimum maximal matching and a minimum edge dominating set always have the same cardinality. ✅

No better algorithm found — O*(1.3160^n) remains the state of the art as of 2025.

Well-written

Several issues found:

1. Decision vs. Optimization Mismatch → Fail

The name MinimumMaximalMatching uses the Minimum prefix (optimization convention in this codebase), but the Definition section gives the G&J decision version with bound K. The Schema includes a bound: usize field matching the decision formulation. This is inconsistent:

• If optimization: remove the bound field, define the objective as "minimize |E'| subject to E' being a maximal matching", and use Value = Min<usize> in implementation
• If feasibility/decision: rename to drop the Minimum prefix (but this contradicts codebase conventions for NP-hard optimization problems)

Recommendation: Rewrite as optimization (minimize |E'|). Drop the bound field from the Schema. This matches the codebase pattern (e.g., MinimumVertexCover, MinimumDominatingSet).

2. Missing Sections → Fail

• No Reduction Rule Crossref section (required when ILP is claimed)
• No Expected Outcome section with an explicit optimal value. The example says "the answer is YES" (decision framing) but should state "optimal value = 2, optimal matching = {(v1,v2), (v3,v4)}" (optimization framing)

3. Complexity Expression Format → Fail

The complexity is stated as prose ("O*(1.3160^n) where n = |V|") but must use a concrete expression in terms of getter method names: 1.3160^num_vertices. This is enforced at compile time by declare_variants!.

4. Example Quality → Warn

The path graph P6 example is adequate (5 edges, multiple maximal matchings of sizes 2 and 3, minimum = 2). However:

• The worked example only shows the YES/NO answer, not the optimization solution
• Should explicitly list all maximal matchings to demonstrate the minimum is 2
• The example has ~3 maximal matchings of varying sizes, which satisfies the round-trip testability requirement

5. Variables Section → Warn

The variables are correctly identified (one binary variable per edge), but the semantic meaning should clarify the optimization objective: "Select the smallest set of edges forming a maximal matching."

Recommendations

• Rewrite the Definition as an optimization problem (drop bound K)
• Add a Reduction Rule Crossref section stating the ILP rule will be implemented together
• Update the complexity to 1.3160^num_vertices
• Update the example to show the optimal value and solution
• Consider mentioning the equivalence to Minimum Edge Dominating Set in the Motivation — this is a well-known connection that adds context

[isPANN]

Fix-issue changelog

• Rewrote Definition from decision (bound K) to optimization framing (minimize |E'|)
• Removed bound field from Schema
• Expanded Motivation with equivalence to Minimum Edge Dominating Set and NP-completeness context
• Clarified Variables section with optimization semantics
• Changed complexity format to 1.3160^num_vertices (getter-method format)
• Enumerated all 4 maximal matchings in the example
• Added Expected Outcome section with optimal value Min(2), optimal + suboptimal solutions
• Added Reduction Rule Crossref section for companion ILP rule
• Removed unverified markers (content now verified)

Applied by /fix-issue.