What is a Vertex Cover?
A vertex cover of a graph is a set of vertices such that every edge has at least one endpoint in the set. The minimum vertex cover is the smallest such set.
This is one of Karp's 21 NP-complete problems, meaning no polynomial-time exact algorithm is known. However, there are efficient approximation algorithms that guarantee solutions within a factor of 2 of optimal.
Algorithms
Edge-Picking 2-Approximation
Pick any uncovered edge, add both endpoints to the cover, remove all edges incident to those vertices. Repeat until no uncovered edges remain. This gives a cover at most 2x the optimal size. The algorithm runs in O(V + E) time and is the simplest known approximation with a provable guarantee.
Weighted Greedy (Best Ratio)
When vertices have weights, a pure edge-picking approach ignores costs. Instead, at each step pick the vertex with the best ratio of uncovered edges per unit weight. Add it to the cover and remove all its incident edges. This heuristic tends to produce good weighted covers in practice.
Vertex Cover vs Related Problems
| Problem | Goal | Complexity |
|---|---|---|
| Min Vertex Cover | Fewest vertices covering all edges | NP-hard (2-approx exists) |
| Max Independent Set | Largest set with no edges between | NP-hard (complement of VC) |
| Min Dominating Set | Fewest vertices within 1 hop of all | NP-hard (no constant approx) |
| Min Edge Cover | Fewest edges covering all vertices | Polynomial (matching-based) |
Frequently Asked Questions
What is a vertex cover?add
A vertex cover of a graph is a set of vertices such that every edge in the graph has at least one endpoint in the set. The minimum vertex cover problem asks for the smallest such set. It is one of the classic NP-hard problems in computer science.
What is the difference between vertex cover and independent set?add
A vertex cover and an independent set are complements. If S is a vertex cover, then V - S (all vertices not in S) is an independent set, and vice versa. Finding the minimum vertex cover is equivalent to finding the maximum independent set. Both problems are NP-hard.
What is the 2-approximation for vertex cover?add
The edge-picking algorithm provides a 2-approximation: repeatedly pick any uncovered edge, add both endpoints to the cover, and remove all edges incident to those vertices. This runs in O(V + E) time and guarantees a cover at most twice the size of the optimal. No better polynomial-time approximation is known unless P = NP.
What is a weighted vertex cover?add
In the weighted version, each vertex has a cost/weight, and the goal is to find a vertex cover with minimum total weight. The greedy approach picks vertices with the best ratio of uncovered edges per unit weight. The pricing (LP relaxation) method provides a 2-approximation for the weighted case as well.
Where are vertex cover problems used in practice?add
Vertex cover appears in network security (monitoring all connections with minimum sensors), bioinformatics (identifying key genes in interaction networks), VLSI design, and scheduling problems. The concept of covering all edges with minimum resources is fundamental in optimization.