Minimum Maximal Matching

Input

Graph $G = (V, E)$, positive integer $K \leq |E|$.

Question

Is there a subset $E' \subseteq E$ with $|E'| \leq 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'$?

Classes

• NP-complete

Comments

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, 1976)).

Proofs

NP-complete

Transformation from Vertex Cover for cubic graphs (Yannakakis & Gavril, 1980).

Reducible from

• Vertex Cover

Reducible to

• Achromatic Number

References

• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.
• Yannakakis, M., & Gavril, F. (1980). Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38(3), 364–372. https://doi.org/10.1137/0138030