Vertex Cover

Imagine a museum where hallways connect rooms, and you want to post guards so that every hallway has a guard at one of its ends. Each guard watches all the hallways touching their room. What's the fewest guards that watch everything?

Turn rooms into nodes and hallways into edges, and you have the vertex cover problem: choose the smallest set of nodes so that every edge has at least one endpoint chosen. It shows up wherever you must "watch", "guard", or "hit" every connection using as few points as possible.

Picking some cover is easy — just take every node. Picking the fewest is where it turns into one of the classic hard problems.

Try it. Click nodes to add them to your cover. An edge turns green when one of its ends is chosen and stays red while it's still uncovered. Cover every edge using as few nodes as you can.

<p class="hint">{{hint}}</p>
<svg id="g" viewBox="0 0 360 250" role="img" aria-label="{{graph_aria}}">
  <g id="edges" stroke-width="3"></g>
  <g id="nodes"></g>
</svg>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="approx" type="button">{{btn_approx}}</button>
  <button id="opt" type="button">{{btn_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .5rem; line-height: 1.45; }
svg { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto; }
.nd { cursor: pointer; }
.nlabel { font: 700 13px system-ui; fill: #fff; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 700; min-height: 1.3em; margin: .5rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

Two buttons help you compare. 2-approx uses a famous trick: repeatedly grab any uncovered edge and take both its endpoints — crude, but provably never more than twice the optimum. Optimal searches for the true minimum. Notice the 2-approx often overshoots, yet its guarantee is rock-solid — a recurring theme in how we tame hard problems.

How hard is vertex cover?

• Checking a cover is trivial: scan every edge and confirm an endpoint is chosen.
• Finding the minimum is NP-hard, and the decision form ("is there a cover of size k?") is NP-complete — it was one of Karp's original 21 NP-complete problems.
• But it's unusually friendly. A trivial rule gives a 2-approximation (never worse than twice optimal), and it's fixed-parameter tractable: if the cover is small (size k), you can find it fast even in a huge graph.
• It's a mirror. The nodes not in a minimum vertex cover form a maximum independent set — the same problem seen inside-out, and the gap at the heart of P vs NP.

So vertex cover is hard in the worst case, yet one of the most approachable hard problems we know.

Anywhere you must touch every connection with the fewest chosen points, vertex cover appears:

• Surveillance: the fewest cameras or guards to watch every corridor or street.
• Network monitoring: the fewest routers to place sensors on so every link is observed.
• Conflict detection: the fewest features to disable so every clash disappears.
• Bioinformatics: simplifying interaction networks by removing a minimal set of nodes.
• Telecom: placing equipment to cover every connection at minimum cost.

And because the 2-approximation is so cheap and reliable, these systems get a guaranteed-good answer instantly — even when the perfect one is out of reach.

Vertex cover starts as a guard-placement puzzle and lands among the classic hard problems: finding the true minimum is NP-hard. But it's also a hopeful case study. A rule as blunt as "grab both ends of any uncovered edge" is guaranteed to land within a factor of two — and clever parameterized methods solve it exactly when the cover is small.

It's a reminder that "NP-hard" is the beginning of the story, not the end. Even when perfection is unreachable, the right simple idea can promise you'll never be far off.