Set Cover

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.

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">{{hint}}</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">{{btn_greedy}}</button>
  <button id="opt" type="button">{{btn_opt}}</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 .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; }

// Code not found

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.

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.

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.

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.