Dominating Set

Imagine a city map drawn as a graph: each junction is a dot, each street an edge. You want to place security cameras so that every junction is either watched directly or sits next to a watched one — and, because cameras cost money, you want to use as few as possible.

That chosen handful of junctions is called a dominating set: a set of vertices such that every other vertex is adjacent to at least one of them. The smallest possible one defines the graph's domination number.

The rule sounds almost trivial. Yet the moment you ask for the smallest dominating set, you walk straight into one of the hardest families of problems in computer science — the same wall behind facility placement, sensor networks and a dozen real engineering decisions.

Below is a small network. Click a vertex to select it; a selected vertex covers itself and every neighbor it touches. Your goal is to light up every vertex — and to do it with no more than the target number of picks.

<p class="hint">{{hint}}</p>
<svg id="graph" viewBox="0 0 320 240" aria-label="{{aria_graph}}"></svg>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="find" type="button">{{btn_find}}</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 .7rem; line-height: 1.45; }
#graph { width: 100%; max-width: 360px; height: auto; display: block; margin: .2rem 0; }
.edge { stroke: #adb1b8; stroke-width: 2; }
.node { fill: #c9ccd1; stroke: #8b9099; stroke-width: 2; cursor: pointer; transition: fill .12s; }
.node.covered { fill: #8fd0a5; stroke: #2f9c5a; }
.node.picked { fill: #1d3557; stroke: #12233b; }
.node:hover { stroke: #1d3557; }
.nlabel { font: 700 12px ui-monospace, monospace; fill: #1d3557; pointer-events: none; }
.node.picked + .nlabel, text.on-dark { fill: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a choice is effortless: light each picked vertex and its neighbors, then see if anything stays dark. Finding the smallest covering set is the hard part — press Find minimum and the computer simply tries every subset of vertices, smallest first. With eight vertices that is 256 combinations; add a few more and the count doubles each time.

How hard is Dominating Set, really? Not checking an answer — finding the best one.

• Checking a candidate set is trivial: mark every chosen vertex and its neighbors, then confirm nothing is left uncovered.
• Brute force tries every subset of vertices — $2^{n}$ possibilities, hopeless once there are more than a few dozen nodes.
• It's NP-complete. The decision version — "is there a dominating set of size at most k?" — is one of the classic NP-complete problems, provable by reduction from Set Cover (and through it from the whole NP family that includes SAT).
• Even approximating is hard. Dominating Set is essentially Set Cover in disguise, so unless P = NP you cannot guarantee a solution better than a factor of about ln n times optimal — and that bound is the best achievable.

That is the punchline: there is no known clever shortcut. The greedy heuristic — repeatedly grab the vertex that newly covers the most — is fast and usually decent, but it can be forced off the true minimum, and closing that gap is exactly as hard as anything in NP.

"Place the fewest resources so everything is covered" is one of the most common shapes a real problem can take, and Dominating Set is its purest form:

• Facility and sensor placement: where to put fire stations, charging points or monitoring sensors so every location is served by at least one nearby.
• Wireless networks: a connected dominating set acts as a virtual backbone — a small set of relay nodes that every other device can reach in one hop.
• Social influence: seeding a campaign at a small set of people whose neighborhoods together cover the whole network.
• Operations and logistics: positioning depots, guards or service points to dominate a region at minimum cost.

Learn why Dominating Set is hard and you've met the covering family — closely tied to Set Cover and the broader question of P vs NP.

Dominating Set hides a familiar tension: verifying that a handful of vertices covers everything is instant, yet deciding whether fewer could do the job is as hard as any problem we know. The minimum we crave may require, in the worst case, checking essentially every possibility.

So the next time a planner agonizes over where to put one more tower, sensor or station, remember there is real mathematics behind the headache. That "obvious" question of covering everything cheaply is P vs NP wearing a city map — and there may be no shortcut to the perfect answer at all.