Introduction

Imagine a tangle of arrows: tasks that wait on each other, web pages that link in circles, processes that hold a resource while waiting for another. Whenever such a network contains a cycle, something can go wrong — a deadlock, an infinite loop, a circular dependency that never resolves.

The cure is to remove a few nodes so that no cycle survives. A graph with no cycles is a forest (a collection of trees), and a forest can always be sorted, scheduled or traversed without ever looping back on itself.

A feedback vertex set is exactly such a rescue squad: a set of vertices whose deletion leaves the graph acyclic. The interesting question is the minimum one — what is the smallest number of vertices we must remove to break every loop? That little number turns out to sit on the boundary between the easy and the genuinely hard.

Break the Cycles

Here is a small graph riddled with loops. Your job is to click vertices to delete them until the remaining graph has no cycle at all — until it is a forest. The panel keeps a live count of how many cycles still survive.

<p class="hint">This graph is full of loops. <b>Click a vertex to delete it</b> (click again to restore). Keep deleting until <b>no cycle survives</b> — until the graph is a forest. Checking is easy; finding the smallest such set is the hard part.</p>
<svg id="graph" viewBox="0 0 320 240" class="graph"></svg>
<div class="status" id="status">Cycles remaining: …</div>
<div class="btns">
  <button id="find" type="button">Find minimum</button>
  <button id="reset" type="button" class="ghost">Restore all</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: .3rem auto;
         background: #f3f6f9; border: 1px solid #dbe3ea; border-radius: 10px; }
.edge { stroke: #9fb0c0; stroke-width: 2.5; }
.edge.dead { stroke: #d8dee4; stroke-dasharray: 4 4; }
.node { cursor: pointer; }
.node circle { fill: #1d3557; stroke: #142540; stroke-width: 2; transition: all .12s; }
.node:hover circle { fill: #2a4d7a; }
.node.removed circle { fill: #fff; stroke: #c9ccd1; stroke-dasharray: 3 3; }
.node text { fill: #fff; font: 700 13px ui-monospace, monospace; pointer-events: none;
             text-anchor: middle; dominant-baseline: central; }
.node.removed text { fill: #adb1b8; }
.status { font-size: 1.05rem; font-weight: 700; margin: .5rem 0; min-height: 1.4em; color: #c92f3c; }
.status.ok { color: #0a7d33; }
.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] ?? ''));
// Feedback vertex set: delete vertices until the graph has no cycle (is a forest).
// Checking is cheap (a DFS for back-edges). Finding the MINIMUM set is NP-hard (Karp, 1972) — here we brute-force every subset smallest-first. It IS fixed-
// parameter tractable: the cost explodes in the answer size k, not the graph size.
const NODES = [
  {id:0,x:70,y:45},{id:1,x:160,y:50},{id:2,x:120,y:120},
  {id:3,x:250,y:120},{id:4,x:200,y:185},{id:5,x:290,y:185},
  {id:6,x:60,y:175}
];
// Undirected edges. Two loops with no shared cut vertex, so the minimum
// feedback vertex set has size 2 (e.g. {0,4}); no single deletion suffices.
const EDGES = [
  [0,1],[1,2],[2,0],      // triangle {0,1,2}
  [3,4],[4,5],[5,3],      // triangle {3,4,5}
  [1,4],                  // bridge between the loops
  [0,6],[6,3],            // path 0-6-3
  [2,5]                   // cross edge
];
const removed = new Set();

// Count independent cycles in the graph induced by the kept vertices.
// For an undirected graph: cyclomatic number = E - V + C (connected components). Zero means acyclic (a forest).
function cycleCount(rem){
  const kept = NODES.filter(n=>!rem.has(n.id)).map(n=>n.id);
  const keptSet = new Set(kept);
  const es = EDGES.filter(([a,b])=>keptSet.has(a)&&keptSet.has(b));
  const V = kept.length, E = es.length;
  // components via union-find
  const parent = {}; kept.forEach(v=>parent[v]=v);
  const find = x => { while(parent[x]!==x){ parent[x]=parent[parent[x]]; x=parent[x]; } return x; };
  es.forEach(([a,b])=>{ parent[find(a)]=find(b); });
  let C = 0; kept.forEach(v=>{ if(find(v)===v) C++; });
  return E - V + C; // independent cycles
}
const isForest = rem => cycleCount(rem) === 0;

function render(){
  const svg = document.getElementById('graph'); svg.innerHTML='';
  const ns='http://www.w3.org/2000/svg';
  EDGES.forEach(([a,b])=>{
    const dead = removed.has(a)||removed.has(b);
    const A=NODES[a], B=NODES[b];
    const l=document.createElementNS(ns,'line');
    l.setAttribute('x1',A.x); l.setAttribute('y1',A.y);
    l.setAttribute('x2',B.x); l.setAttribute('y2',B.y);
    l.setAttribute('class','edge'+(dead?' dead':'')); svg.appendChild(l);
  });
  NODES.forEach(n=>{
    const g=document.createElementNS(ns,'g');
    g.setAttribute('class','node'+(removed.has(n.id)?' removed':''));
    g.addEventListener('click',()=>{ removed.has(n.id)?removed.delete(n.id):removed.add(n.id); render(); });
    const c=document.createElementNS(ns,'circle');
    c.setAttribute('cx',n.x); c.setAttribute('cy',n.y); c.setAttribute('r',16);
    const t=document.createElementNS(ns,'text');
    t.setAttribute('x',n.x); t.setAttribute('y',n.y); t.textContent=n.id;
    g.appendChild(c); g.appendChild(t); svg.appendChild(g);
  });
  updateStatus();
}
function updateStatus(){
  const s=document.getElementById('status');
  const cyc=cycleCount(removed);
  if(cyc===0){ s.textContent=fmt('No cycles left — it is a forest! Deleted %size% vertices.', { size: removed.size }); s.className='status ok'; }
  else { s.textContent=fmt('Cycles remaining: %cyc% (deleted %size%).', { cyc: cyc, size: removed.size }); s.className='status'; }
}
// Brute force: try every subset, smallest first; first acyclic one is minimum.
function findMin(){
  const ids = NODES.map(n=>n.id), n=ids.length;
  let best=null, checked=0;
  for(let k=0;k<=n && !best;k++){
    // enumerate all subsets of size k
    const idx=[]; for(let i=0;i<k;i++) idx.push(i);
    while(true){
      checked++;
      const cand=new Set(idx.map(i=>ids[i]));
      if(isForest(cand)){ best=cand; break; }
      // next combination
      let p=k-1;
      while(p>=0 && idx[p]===n-k+p) p--;
      if(p<0) break;
      idx[p]++; for(let q=p+1;q<k;q++) idx[q]=idx[q-1]+1;
    }
  }
  if(best){
    removed.clear(); best.forEach(v=>removed.add(v)); render();
    const s=document.getElementById('status');
    s.textContent=fmt('Minimum feedback vertex set: {%sort%} — size %size%. Checked %checked% subsets.', { sort: [...best].sort((a,b)=>a-b).join(', '), size: best.size, checked: checked });
    s.className='status ok';
    console.log('Minimum FVS:', [...best].sort((a,b)=>a-b), '|', 'size', best.size, '|', 'subsets checked', checked);
  }
}
document.getElementById('find').addEventListener('click',findMin);
document.getElementById('reset').addEventListener('click',()=>{ removed.clear(); render(); });
render();
Result
Console

Notice the asymmetry. Checking a candidate is easy: delete the chosen vertices, then test whether anything that is left still loops. Finding the minimum is the hard part — press Find minimum and the computer tries every subset of vertices, smallest first, until one of them kills every cycle. With a handful of nodes that is quick; double the graph and the number of subsets explodes.

The Real Complexity

How hard is it to find the minimum feedback vertex set?

  • Checking a candidate set is trivial: remove those vertices and run a quick cycle test on what remains — linear time.
  • Brute force tries every subset of vertices, 2n2^{n} of them, hopeless once the graph has more than a few dozen nodes.
  • It is NP-hard. Minimum Feedback Vertex Set was one of Richard Karp's 21 NP-complete problems in 1972, so no known algorithm solves the general case efficiently — and finding one would settle P vs NP.
  • But it is fixed-parameter tractable (FPT). Here is the twist: if you only care about whether a feedback vertex set of size k exists, the problem can be solved in time f(k) · poly(n) — the exponential blow-up is confined to k, not the whole graph. The best deterministic algorithms run in roughly 3.6ᵏ · poly(n), and a beautiful randomized method gets it down further. When k is small, the problem is genuinely fast.

That is the punchline: the difficulty is not really in the size of the graph but in the size of the answer. As long as a few deletions suffice, modern parameterized algorithms find them quickly — a striking contrast with cousins like vertex cover and graph coloring that share the same NP-hard core.

Where It Matters

"Remove as little as possible so that nothing loops" is a question that surfaces all over computing:

  • Deadlock recovery: an operating system that detects a circular wait among processes must abort the fewest of them to break the cycle — a feedback vertex set on the wait-for graph.
  • Chip design and testing: cutting feedback loops in a circuit (placing scan registers) makes a sequential circuit far easier to test; designers want to cut as few signals as possible.
  • Program analysis and compilers: breaking cycles in control-flow or dependency graphs simplifies loop optimization and termination reasoning.
  • Bayesian network inference: the cutset conditioning method makes a probabilistic network tractable by conditioning on a small feedback vertex set, turning a loopy graph into a tree.

Master why feedback vertex set is hard and you have met parameterized complexity — the idea that a problem's difficulty often hinges on a single small number, not the raw input size.

Conclusion

Feedback Vertex Set tells a hopeful story. In full generality it is NP-hard — one of the original problems Karp proved intractable in 1972 — so we do not expect a fast algorithm that scales to every graph. Yet the moment we ask the practical question — "can a small set of deletions do the job?" — the problem becomes fixed-parameter tractable, and clever algorithms find the answer quickly.

So the next time a system tangles itself into circular dependencies, take comfort: cutting the loops may be theoretically hard, but if only a few cuts are needed — and in practice they usually are — the solution is well within reach. It is a reminder that "NP-hard" is the start of the story, not the end. For the bigger picture, see P vs NP.

Share this article

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

Comments

Loading comments...

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