Introduction

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.

Try It: Cover the Graph

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">Click a vertex to <b>pick</b> it. A picked vertex lights itself and every neighbor it touches. Light up <b>all</b> vertices — and try to do it with no more than the <b>target</b> number of picks. Checking coverage is instant; finding the smallest covering set is the hard part.</p>
<svg id="graph" viewBox="0 0 320 240" aria-label="network"></svg>
<div class="status" id="status">Picked 0 — target 3. Cover every vertex.</div>
<div class="btns">
  <button id="check" type="button">Check coverage</button>
  <button id="find" type="button">Find minimum</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimum Dominating Set: pick a set S of vertices so that every vertex is in S or adjacent to a vertex in S. Checking one choice is a quick scan; finding the smallest S in general is NP-hard (decision version is NP-complete; it reduces to/from Set Cover). Brute force here tries subsets smallest-first: 2^n choices.
const N = 8, TARGET = 3;
// Vertex positions (for drawing only).
const POS = [
  [60,50],[160,40],[260,55],[40,140],
  [160,130],[280,140],[100,210],[230,205]
];
// Adjacency list. Designed so the minimum dominating set has size 3: {1,3,7} (0-indexed) — vertex 1 covers 0,2,4; vertex 3 covers 6; vertex 7 covers 5,7,4...
const ADJ = [
  [1,3],        // 0
  [0,2,4],      // 1
  [1,5],        // 2
  [0,6],        // 3
  [1,5,7],      // 4
  [2,4,7],      // 5
  [3,7],        // 6
  [4,5,6]       // 7
];
const picked = new Set();

// closed neighborhood: a picked vertex covers itself + its neighbors
function coveredBy(set){
  const cov = new Set();
  set.forEach(v => { cov.add(v); ADJ[v].forEach(u => cov.add(u)); });
  return cov;
}
function allCovered(set){ return coveredBy(set).size === N; }

function draw(){
  const cov = coveredBy(picked);
  let svg = '';
  const seen = new Set();
  for(let v=0; v<N; v++) for(const u of ADJ[v]){
    const key = v<u ? v+'-'+u : u+'-'+v;
    if(seen.has(key)) continue; seen.add(key);
    svg += `<line class="edge" x1="${POS[v][0]}" y1="${POS[v][1]}" x2="${POS[u][0]}" y2="${POS[u][1]}"/>`;
  }
  for(let v=0; v<N; v++){
    const cls = picked.has(v) ? 'picked' : (cov.has(v) ? 'covered' : '');
    const tcls = picked.has(v) ? 'on-dark' : '';
    svg += `<circle class="node ${cls}" data-v="${v}" cx="${POS[v][0]}" cy="${POS[v][1]}" r="16"/>`;
    svg += `<text class="nlabel ${tcls}" x="${POS[v][0]}" y="${POS[v][1]+4}" text-anchor="middle">${v}</text>`;
  }
  const g = document.getElementById('graph');
  g.innerHTML = svg;
  g.querySelectorAll('circle.node').forEach(c =>
    c.addEventListener('click', () => {
      const v = +c.dataset.v;
      picked.has(v) ? picked.delete(v) : picked.add(v);
      draw(); setStatus(fmt('Picked %size% — target %TARGET%. Cover every vertex.', { size: picked.size, TARGET: TARGET }),'');
    }));
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function check(){
  if(!allCovered(picked)){ setStatus('✗ Some vertices are still dark. Keep covering.','bad'); return; }
  if(picked.size <= TARGET) setStatus(fmt('✓ Fully covered with %size% picks — you hit the target!', { size: picked.size }),'ok');
  else setStatus(fmt('✓ Covered, but with %size% picks. Can you reach the target of %TARGET%?', { size: picked.size, TARGET: TARGET }),'bad');
}
function find(){
  // brute force: try every subset, smallest first; return first dominating set
  let best=null, steps=0;
  const idx=[...Array(N).keys()];
  for(let k=0; k<=N && !best; k++){
    const combo=(arr,k)=>{ const res=[]; const rec=(s,c)=>{ if(c.length===k){res.push([...c]);return;}
      for(let i=s;i<arr.length;i++){c.push(arr[i]);rec(i+1,c);c.pop();}}; rec(0,[]); return res; };
    for(const c of combo(idx,k)){ steps++; if(allCovered(new Set(c))){ best=c; break; } }
  }
  picked.clear(); best.forEach(v=>picked.add(v)); draw();
  setStatus(fmt('Minimum dominating set has size %v% (vertices %best%), found after testing %steps% subsets.', { v: best.size||best.length, best: best.join(', '), steps: steps }),'ok');
  console.log('min dominating set:', best, '| subsets tested:', steps);
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('find').addEventListener('click',find);
document.getElementById('reset').addEventListener('click',()=>{ picked.clear(); draw(); setStatus(fmt('Picked 0 — target %TARGET%. Cover every vertex.', { TARGET: TARGET }),''); });
draw();
Result
Console

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.

The Real Complexity

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 — 2n2^{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.

Where It Matters

"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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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