🛡️ 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(2^k) 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.