🎯 Vertex Cover (2-Approximation)

Problem (NP-Hard!)

Find the smallest set of vertices that "covers" all edges (every edge has at least one endpoint in the set).

2-Approximation Algorithm:

1. Pick any uncovered edge (u, v)
2. Add BOTH u and v to the cover
3. Remove all edges incident to u or v
4. Repeat until no edges remain

Guarantee: At most 2× optimal size!