[Rule] VERTEX COVER (cubic) to MINIMUM MAXIMAL MATCHING #893
Description
Source: MINIMUM VERTEX COVER (MinimumVertexCover)
Target: MINIMUM MAXIMAL MATCHING (MinimumMaximalMatching)
Motivation: Connects vertex covering to edge-based independent covering, showing that finding a smallest maximal matching is computationally hard. The reduction is an identity map: the same graph G with the same bound K. Every minimum vertex cover of size K implies a maximal matching of size at most K (pick one edge per cover vertex greedily), and every maximal matching of size K gives a vertex cover of size 2K (both endpoints). For the optimization version, the identity map preserves the graph structure and the bound direction is tight enough for witness extraction on general graphs.
Reference: Garey & Johnson, Computers and Intractability, A1.1, GT10; Yannakakis and Gavril (1978).
GJ Source Entry
[GT10] MINIMUM MAXIMAL MATCHING
INSTANCE: Graph G = (V, E), positive integer K ≤ |E|.
QUESTION: Is there a maximal matching for G of size K or less, i.e., a subset E' ⊆ E with |E'| ≤ K such that no two edges in E' share a common endpoint and such that 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.
Reduction Algorithm
Given a MinimumVertexCover instance (G = (V, E)), construct a MinimumMaximalMatching instance as follows:
-
Graph construction: G' = G. Copy the graph unchanged — same vertex set V and edge set E.
-
Forward direction (VC → MMM): Given a vertex cover S ⊆ V of size K, construct a maximal matching greedily: for each vertex v ∈ S, if v is not yet matched, pick any unmatched edge incident to v and add it to the matching. The result is a matching of size ≤ K. It is maximal because every edge has at least one endpoint in S (by the cover property), so every edge is either in the matching or adjacent to a matching edge.
-
Backward direction (MMM → VC): Given a maximal matching M of size K, the set of all 2K endpoints of M is a vertex cover of size ≤ 2K. This is because every edge must share an endpoint with some matching edge (maximality), so every edge is incident to at least one endpoint in the cover. For the exact-value witness extraction, additional care is needed.
-
Solution extraction: From a maximal matching M, extract both endpoints of each matching edge as the vertex cover candidate. If the cover is larger than needed, prune redundant vertices.
Correctness
The identity map preserves the graph structure. The key relationship is:
- mmm(G) ≤ mvc(G) ≤ 2 · mmm(G)
where mmm(G) is the minimum maximal matching size and mvc(G) is the minimum vertex cover size. The forward direction shows mmm(G) ≤ mvc(G), and the backward direction shows mvc(G) ≤ 2 · mmm(G).
Codex verification needed: The derivation claims a factor-2 gap in the backward direction, but PR #992 passed 15K automated checks. Need to test whether extract_solution actually works for general graphs. The greedy forward construction may lose optimality — a minimum vertex cover of size K may yield a maximal matching of size < K, and conversely a minimum maximal matching may not directly give a minimum vertex cover. The reduction is valid for NP-hardness (one direction), and the factor-2 approximation bound holds for the reverse.
Size Overhead
| Target metric (code name) | Expression |
|---|---|
num_vertices |
num_vertices |
num_edges |
num_edges |
Derivation: The graph is copied unchanged. Identity map.
Implementation Note
MinimumMaximalMatching already has a path to ILP (MinimumMaximalMatching/SimpleGraph → ILP/bool). No companion ILP rule is needed.
Example
Source (MinimumVertexCover):
Pentagon graph (cycle C_5) with 5 vertices {0, 1, 2, 3, 4}:
- Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,0}
- Minimum vertex cover size: 3 (e.g., {0, 1, 3})
Target (MinimumMaximalMatching):
- Same pentagon graph: 5 vertices, 5 edges
- Minimum maximal matching size: 2 (e.g., M = {{0,1}, {2,3}})
- Check maximality: edge {4,0} shares endpoint 0 with {0,1} ✓; edge {1,2} shares endpoint 1 with {0,1} ✓; edge {3,4} shares endpoint 3 with {2,3} ✓. All uncovered edges are adjacent to M.
Solution mapping (forward): From VC = {0, 1, 3}:
- Vertex 0: pick edge {0,1}, add to matching
- Vertex 1: already matched
- Vertex 3: pick edge {3,4}, add to matching (edge {2,3} also works)
- Matching M = {{0,1}, {3,4}}, size 2 ≤ 3 ✓
Solution mapping (backward): From MMM = {{0,1}, {2,3}}:
- Endpoints: {0, 1, 2, 3}, size 4 ≤ 2·2 = 4
- Is {0, 1, 2, 3} a vertex cover? Edge {4,0}: vertex 0 ∈ cover ✓. All other edges have both endpoints in cover. Yes ✓.
- But mvc(G) = 3, not 4. The factor-2 gap is visible: mmm = 2, 2·mmm = 4 ≥ 3 = mvc.
Larger example (Petersen graph):
10 vertices, 15 edges, 3-regular:
- mvc = 4, mmm = 4 (equality holds for the Petersen graph)
- The identity map works perfectly here.
Validation Method
- Closed-loop test: reduce MinimumVertexCover to MinimumMaximalMatching, solve target via ILP, extract vertex cover from matching endpoints, verify the cover is valid
- Test on graphs where mmm(G) = mvc(G) (e.g., Petersen graph) and where there is a gap (e.g., pentagon)
- Verify that the factor-2 bound holds across all test cases
References
- Yannakakis, M. and Gavril, F. (1978). "Edge dominating sets in graphs." SIAM Journal on Applied Mathematics, 38(3), pp. 364–372.
- Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability, A1.1, GT10.