Feedback Vertex Set

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.

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">{{hint}}</p>
<svg id="graph" viewBox="0 0 320 240" class="graph"></svg>
<div class="status" id="status">{{cycles_remaining_init}}</div>
<div class="btns">
  <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: .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; }

// Code not found

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.

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, $2^{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.

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

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.