Introduction

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.

Cover Every Edge

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">Click a node to place a "guard" there. An edge turns <b>green</b> when one of its ends has a guard, and stays <b>red</b> while uncovered. Cover <b>every edge</b> using as few guards as you can. This graph can be done with just <b>2</b>.</p>
<svg id="g" viewBox="0 0 360 250" role="img" aria-label="Graph to cover">
  <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">2-approx</button>
  <button id="opt" type="button">Optimal</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimum vertex cover: fewest nodes so every edge has a chosen endpoint.
// NP-hard, but the "grab both ends of an uncovered edge" rule is a 2-approx.
const NODES = { A:{x:110,y:95}, B:{x:250,y:95}, n1:{x:40,y:40}, n2:{x:40,y:170}, n3:{x:180,y:210}, n4:{x:320,y:40}, n5:{x:320,y:170} };
const NAMES = Object.keys(NODES);
const EDGES = [['A','n1'],['A','n2'],['A','n3'],['A','B'],['B','n3'],['B','n4'],['B','n5']];
let cover = new Set();

const covered = e => cover.has(e[0]) || cover.has(e[1]);

function render() {
  const eg = document.getElementById('edges'); eg.innerHTML = '';
  let cov = 0;
  EDGES.forEach(e => {
    const a = NODES[e[0]], b = NODES[e[1]], ok = covered(e); if (ok) cov++;
    const ln = document.createElementNS('http://www.w3.org/2000/svg','line');
    ln.setAttribute('x1',a.x); ln.setAttribute('y1',a.y); ln.setAttribute('x2',b.x); ln.setAttribute('y2',b.y);
    ln.setAttribute('stroke', ok ? '#2a9d8f' : '#e63946');
    eg.appendChild(ln);
  });
  const ng = document.getElementById('nodes'); ng.innerHTML = '';
  NAMES.forEach(name => {
    const p = NODES[name], on = cover.has(name);
    const c = document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx',p.x); c.setAttribute('cy',p.y); c.setAttribute('r',20);
    c.setAttribute('fill', on ? '#457b9d' : '#adb5bd'); c.setAttribute('stroke','#fff'); c.setAttribute('stroke-width',2);
    c.setAttribute('class','nd');
    c.addEventListener('click', () => { cover.has(name) ? cover.delete(name) : cover.add(name); render(); });
    ng.appendChild(c);
    const t = document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x',p.x); t.setAttribute('y',p.y); t.setAttribute('class','nlabel'); t.textContent = name;
    ng.appendChild(t);
  });
  const st = document.getElementById('status');
  if (cov < EDGES.length) { st.className='status bad'; st.textContent = fmt('%cov% of %length% edges covered — fix the red ones (%size% guards used).', { cov: cov, length: EDGES.length, size: cover.size }); }
  else if (cover.size <= 2) { st.className='status ok'; st.textContent = fmt('All edges covered with %size% guards — that’s the minimum! 🎉', { size: cover.size }); }
  else { st.className='status ok'; st.textContent = fmt('All edges covered with %size% guards. The minimum is 2 — can you trim it?', { size: cover.size }); }
}

function approx() {
  cover = new Set();
  for (const e of EDGES) if (!covered(e)) { cover.add(e[0]); cover.add(e[1]); }
  render();
  console.log(fmt('2-approx cover size %size% (optimal 2).', { size: cover.size }));
}
function optimal() {
  let best = null;
  for (let m = 0; m < (1 << NAMES.length); m++) {
    const s = new Set(NAMES.filter((_, i) => m & (1 << i)));
    if (EDGES.every(e => s.has(e[0]) || s.has(e[1])) && (best === null || s.size < best.size)) best = s;
  }
  cover = best; render();
}
document.getElementById('approx').addEventListener('click', approx);
document.getElementById('opt').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { cover = new Set(); render(); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/vertex-cover/Content licensed under CC BY-NC 4.0.