Skip to main content
← All Solvers

# 🛡️ Vertex Cover

Band 5 — The Mars transformer. Find the smallest set of vertices that touches every edge.

Vertices: 15 Edge density: 40%
Ready

### Algorithm: Greedy Approximation (2-approximation)

Pick an edge, add both endpoints to the cover, remove all edges incident to them, repeat. This guarantees a cover at most 2× the optimal size. O(V+E) time. For exact solutions, branch-and-bound runs in O(2k) where k is the cover size.

### Why This Matters

Vertex Cover governs network defense — surveillance camera placement, network security, supply chain vulnerability. The Mars transformer covers all exposed points.