Introduction

A city wants every neighborhood reached by emergency services. Each fire station covers a certain set of neighborhoods, and stations are expensive. What is the fewest stations that together cover every neighborhood?

Strip away the story and you get the set cover problem: given a universe of items and a collection of sets (each covering some items), choose the fewest sets whose union is everything. Skills to cover for a project, tests to cover every feature, sensors to cover every zone — they're all set cover.

Picking some cover is easy. Picking the fewest is one of the most fundamental hard problems — and the close cousin of vertex cover.

Cover Everything

Try it. Six items need covering, and you have several sets to choose from. Click a set to add it; the items it covers light up green. Cover all six using as few sets as you can.

<p class="hint">Six items (1–6) must all be covered. Each set below covers some of them. Click sets to add them; covered items turn green. Cover <b>all six</b> using as <b>few sets</b> as possible.</p>
<div class="universe" id="universe"></div>
<div class="sets" id="sets"></div>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="greedy" type="button">Greedy</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 .6rem; line-height: 1.45; }
.universe { display: flex; gap: .4rem; margin-bottom: .7rem; }
.item { width: 40px; height: 40px; border-radius: 8px; background: #e9ecef; border: 2px solid #ccc; display: flex; align-items: center; justify-content: center; font: 700 16px ui-monospace, monospace; color: #888; transition: all .12s; }
.item.cov { background: #2a9d8f; border-color: #2a9d8f; color: #fff; }
.sets { display: grid; grid-template-columns: repeat(auto-fill, minmax(120px, 1fr)); gap: .5rem; }
.set { border: 2px solid #ddd; border-radius: 10px; padding: .5rem .6rem; cursor: pointer; background: #fff; transition: all .12s; user-select: none; }
.set.on { border-color: #457b9d; background: #eaf1f6; box-shadow: 0 2px 8px rgba(69,123,157,.2); }
.set .nm { font-weight: 700; font-size: .95rem; }
.set .el { font: 13px ui-monospace, monospace; color: #555; margin-top: .2rem; }
.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] ?? ''));
// Set cover: fewest sets whose union is the whole universe. NP-hard; the greedy
    // "cover the most uncovered" rule is within ln n of optimal (and that's the best possible).
const UNIVERSE = [1, 2, 3, 4, 5, 6];
const SETS = [
  { id: 'A', el: [1, 2, 3] }, { id: 'B', el: [4, 5, 6] }, { id: 'C', el: [2, 3, 4, 5] },
  { id: 'D', el: [1, 2] }, { id: 'E', el: [5, 6] },
];
let chosen = new Set();

const coveredItems = () => { const s = new Set(); SETS.forEach(S => { if (chosen.has(S.id)) S.el.forEach(e => s.add(e)); }); return s; };

function render() {
  const cov = coveredItems();
  const uni = document.getElementById('universe'); uni.innerHTML = '';
  UNIVERSE.forEach(n => { const d = document.createElement('div'); d.className = 'item' + (cov.has(n) ? ' cov' : ''); d.textContent = n; uni.appendChild(d); });
  const box = document.getElementById('sets'); box.innerHTML = '';
  SETS.forEach(S => {
    const el = document.createElement('div');
    el.className = 'set' + (chosen.has(S.id) ? ' on' : '');
    el.innerHTML = fmt('<div class="nm">Set %id%</div><div class="el">{ %el% }</div>', { id: S.id, el: S.el.join(', ') });
    el.addEventListener('click', () => { chosen.has(S.id) ? chosen.delete(S.id) : chosen.add(S.id); render(); });
    box.appendChild(el);
  });
  const st = document.getElementById('status');
  const c = cov.size, k = chosen.size;
  if (c < UNIVERSE.length) { st.className = 'status bad'; st.textContent = fmt('%c% of %length% items covered with %k% set(s) — keep going.', { c: c, length: UNIVERSE.length, k: k }); }
  else if (k <= 2) { st.className = 'status ok'; st.textContent = fmt('All covered with %k% sets — that’s the minimum! 🎉', { k: k }); }
  else { st.className = 'status ok'; st.textContent = fmt('All covered with %k% sets. The minimum is 2 — can you trim it?', { k: k }); }
}

function greedy() {
  chosen = new Set(); const cov = new Set();
  while (cov.size < UNIVERSE.length) {
    let best = null, gain = -1;
    for (const S of SETS) { if (chosen.has(S.id)) continue; const g = S.el.filter(e => !cov.has(e)).length; if (g > gain) { gain = g; best = S; } }
    if (!best || gain === 0) break;
    chosen.add(best.id); best.el.forEach(e => cov.add(e));
  }
  render();
  console.log(fmt('Greedy used %size% sets: %v% (optimal 2).', { size: chosen.size, v: [...chosen].join(', ') }));
}
function optimal() {
  let best = null;
  for (let m = 1; m < (1 << SETS.length); m++) {
    const pick = SETS.filter((_, i) => m & (1 << i));
    const u = new Set(); pick.forEach(S => S.el.forEach(e => u.add(e)));
    if (u.size === UNIVERSE.length && (best === null || pick.length < best.length)) best = pick;
  }
  chosen = new Set(best.map(S => S.id)); render();
}
document.getElementById('greedy').addEventListener('click', greedy);
document.getElementById('opt').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { chosen = new Set(); render(); });
render();
Result
Console

Then compare. Greedy repeatedly grabs the set that covers the most still-uncovered items — sensible, and it often works. But watch: greedy can be lured by a big overlapping set and end up using more than the optimum. Optimal finds the true fewest. The gap between them is exactly where the difficulty lives.

The Real Complexity

How hard is set cover?

  • Checking a cover is trivial: take the union of the chosen sets and confirm nothing is missing.
  • Finding the fewest is NP-hard — one of Karp's original 21, and a generalization of vertex cover.
  • Greedy is famously good — its cover is never more than about ln n times optimal (n = number of items).
  • And that's the ceiling. A deep result shows that no efficient algorithm can do essentially better than ln n unless P = NP. Greedy isn't just a decent heuristic here — it's provably the best we can hope for.

Set cover is the rare problem where the simple greedy rule is also the theoretical champion.

Where It Matters

Anywhere "use the fewest things that cover all requirements" appears, it's set cover:

  • Facility & service placement: fewest stations, warehouses, or antennas to reach every area.
  • Sensor and camera coverage: fewest devices to monitor every zone.
  • Software testing: smallest set of test cases that exercises every feature or line.
  • Feature selection: fewest attributes that distinguish all the cases in a dataset.
  • Crew and skill assignment: fewest people whose combined skills cover every required task.

Because greedy is both fast and provably near-best, set cover is one of the most practical NP-hard problems to live with.

Conclusion

Set cover asks the plainest of questions — what's the fewest pieces that cover everything? — and answers with one of computer science's most elegant facts. The minimum is NP-hard to find, yet the obvious greedy rule lands within a logarithmic factor, and no efficient method can promise better.

It's a satisfying twist on this site's recurring theme. Usually the simple greedy heuristic is a compromise. For set cover, it's the champion: the best the limits of algorithms will ever allow.

Share this article

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

Comments

Loading comments...

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