[Model] VertexCover #986
Description
Motivation
VERTEX COVER is one of Karp's 21 NP-complete problems (1972) and the canonical decision version of the existing MinimumVertexCover. Including the decision formulation enables classical complexity-theoretic reductions in their standard form (e.g., 3-SAT → VertexCover from Garey & Johnson Theorem 3.3).
Definition
Name: VertexCover
Reference: Karp, "Reducibility Among Combinatorial Problems", 1972; Garey & Johnson, Computers and Intractability, 1979, GT1
Given an undirected graph G = (V, E) and a positive integer k ≤ |V|, is there a vertex cover of size k or less for G, i.e., a subset V' ⊆ V with |V'| ≤ k such that for each edge {u, v} ∈ E, at least one of u and v belongs to V'?
Variables
- Count: n = |V| (one variable per vertex)
- Per-variable domain: {0, 1}
- Meaning: x_i = 1 if vertex i ∈ V' (selected in cover), 0 otherwise. A configuration is feasible if it forms a vertex cover (every edge has at least one endpoint selected) and the number of selected vertices is at most k.
Schema (data type)
Type name: VertexCover
Variants: (SimpleGraph) — unweighted, simple graph input
| Field | Type | Description |
|---|---|---|
graph |
SimpleGraph | The input graph G = (V, E) |
k |
positive integer | Threshold — maximum allowed cover size |
Complexity
- Best known exact algorithm: O(1.1996^n) where n = |V|, by Chen, Kanj, and Xia (2010). Same as MinimumVertexCover since solving the optimization version answers any decision query.
- References: J. Chen, I.A. Kanj, G. Xia, "Improved Upper Bounds for Vertex Cover", Theoretical Computer Science, Vol. 411, Issues 40–42, pp. 3736–3756, 2010. https://doi.org/10.1016/j.tcs.2010.06.026
Extra Remark
This is the decision version of MinimumVertexCover (GT1 in Garey & Johnson). The optimization version finds the minimum-weight cover; this version asks whether a cover of size ≤ k exists. Vertex Cover was one of the original 21 problems shown NP-complete by Karp (1972), via reduction from Satisfiability.
Reduction Rule Crossref
- [Rule] VertexCover to MinimumVertexCover #987 [Rule] VertexCover to MinimumVertexCover — solvability path (VertexCover → MVC → ILP)
- [Rule] KSatisfiability to VertexCover #988 [Rule] KSatisfiability to VertexCover — NP-hardness proof from 3-SAT (Garey & Johnson Theorem 3.3)
How to solve
- It can be solved by (existing) brute force. (Enumerate all 2^|V| binary vertex selections; check cover validity and size ≤ k.)
- It can be solved by reducing directly to ILP via #issue-number.
- Other: Reduce to MinimumVertexCover (companion rule), which has an existing path to ILP.
Example Instance
Graph G with 4 vertices {0, 1, 2, 3} and 4 edges: {0,1}, {1,2}, {0,2}, {2,3} (triangle on {0,1,2} with pendant edge to vertex 3). k = 2.
Expected Outcome
k = 2, YES: Vertex cover V' = {0, 2} — edge {0,1} covered by 0, edge {1,2} covered by 2, edge {0,2} covered by 0, edge {2,3} covered by 2. |V'| = 2 ≤ k. Valid.
k = 1, NO: The triangle {0,1,2} has 3 edges; any single vertex covers at most 2 of 3 triangle edges, so at least 2 vertices are required.
Python validation script
from itertools import combinations
edges = [(0,1), (1,2), (0,2), (2,3)]
n = 4
def is_vertex_cover(verts, edges):
cover = set(verts)
return all(u in cover or v in cover for u, v in edges)
# Find minimum vertex cover by brute force
for size in range(n + 1):
for combo in combinations(range(n), size):
if is_vertex_cover(combo, edges):
print(f"Minimum vertex cover: {combo}, size: {size}")
assert size == 2
break
else:
continue
break
# k=2: YES
assert any(is_vertex_cover(c, edges) for c in combinations(range(n), 2))
print("k=2: YES ✓")
# k=1: NO
assert not any(is_vertex_cover(c, edges) for c in combinations(range(n), 1))
print("k=1: NO ✓")BibTeX
@incollection{Karp1972,
author = {Richard M. Karp},
title = {Reducibility Among Combinatorial Problems},
booktitle = {Complexity of Computer Computations},
publisher = {Plenum Press},
year = {1972},
pages = {85--103},
}
@book{GareyJohnson1979,
author = {Michael R. Garey and David S. Johnson},
title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
publisher = {W.H. Freeman},
year = {1979},
}
@article{ChenKanjXia2010,
author = {Jianer Chen and Iacono A. Kanj and Ge Xia},
title = {Improved Upper Bounds for Vertex Cover},
journal = {Theoretical Computer Science},
volume = {411},
number = {40--42},
pages = {3736--3756},
year = {2010},
doi = {10.1016/j.tcs.2010.06.026},
}