Parameterised Complexity and FPT

"NP-hard" measures difficulty against a single yardstick: the input size n. But that yardstick is crude. Two instances of the same size can be worlds apart in difficulty, and the thing that makes one easy is often some second quantity — the size of the solution you're looking for, how tree-like the graph is, how many constraints you'd need to delete. Parameterised complexity, launched by Downey and Fellows, is the theory that takes that second quantity seriously. It is the sharpest tool in the coping kit for problems where a natural parameter stays small.

The payoff is a running time like 2^k \cdot n: exponential, yes — but the explosion is confined to the small parameter k, while the large quantity n enters only polynomially. When k=20 and n = 10^7, that is the difference between an answer over lunch and the heat death of the universe.

FPT versus XP: where the parameter sits

A parameterised problem attaches a parameter k to each input of size n. Two very different notions of "efficient" arise, and the whole subject turns on the difference:

FPT (fixed-parameter tractable): solvable in f(k)\cdot n^{O(1)} — the exponential blowup f(k) depends on k alone, multiplied by a polynomial in n whose degree is fixed. Example: 2^k n, or 1.28^k + n^3.
XP (slice-wise polynomial): solvable in n^{f(k)} — for each fixed k it is polynomial, but the degree grows with k. Example: n^{k} — the brute-force "try all size-k subsets" algorithm.

The distinction is everything. n^k with k = 20 and n = 10^6 is 10^{120} — hopeless. But 2^k n = 2^{20}\cdot 10^6 \approx 10^{12} — a few minutes. FPT keeps k and n in separate factors; XP lets k climb into n's exponent, where it does ruinous damage. Every parameterised algorithm designer is trying to move a problem from XP down into FPT.

Vertex Cover is FPT: a bounded search tree

The decision question "is there a vertex cover of size \le k?" is FPT by a gorgeous argument. Take any edge (u,v): every cover must contain u or v. So branch — recurse twice, once putting u in the cover, once v — and in each branch the budget drops by one.

// Is there a vertex cover of size ≤ k? Runs in O(2^k · n) time. function vcFPT(edges: [number, number][], k: number): boolean { if (edges.length === 0) return true; // everything covered if (k === 0) return false; // budget spent, edges remain const [u, v] = edges[0]; // pick any uncovered edge const without = (x: number) => edges.filter(([a, b]) => a !== x && b !== x); return vcFPT(without(u), k - 1) // branch 1: take u || vcFPT(without(v), k - 1); // branch 2: take v }

The recursion tree has depth at most k and branches two ways, so it has at most 2^k leaves, and each node does O(n) work: total O(2^k n). The exponential is nailed to k; n is merely linear. The figure grows this search tree level by level — watch the leaf count double each time, capped at 2^k no matter how large the graph.

Clever branching does even better — analysing high-degree vertices first drives the base below 2, to around 1.28^k. But the shape is the point: a search tree whose size is a function of k only.

Kernelisation: shrink the instance first

The second pillar of FPT is kernelisation — polynomial-time preprocessing that provably shrinks an instance down to a size bounded by a function of k alone (the kernel), after which even brute force is fast. A theorem ties it all together: a problem is FPT if and only if it has a kernel.

Any vertex of degree > k must be in every size-k cover (else its >k edges would need >k other vertices). Put it in the cover, delete it, and drop k by one.
Discard isolated vertices. After exhaustive application, every remaining vertex has degree \le k, so k cover vertices touch at most k^2 edges. If more edges remain, answer NO; otherwise at most k^2 edges and (a sharper argument) \le 2k vertices survive.

You are left with a \le 2k-vertex kernel independent of the original n — solve that however you like. Kernelisation is why FPT algorithms are fast in practice as well as theory: the expensive step runs on a tiny residue.

Treewidth, and the "not-FPT" frontier: W[1]-hardness

Treewidth measures how close a graph is to a tree; a width-w tree decomposition lets dynamic programming sweep the graph solving countless NP-hard problems in 2^{O(w)}\cdot n time — FPT parameterised by treewidth. Bounded treewidth is one of the most fruitful parameters in the whole theory: real inputs (control-flow graphs, series-parallel networks) often have small width.

But not everything is FPT. Just as NP-completeness marks the likely-intractable decision problems, W[1]-hardness marks the likely-not-FPT parameterised problems. The canonical W[1]-complete problem is Clique parameterised by clique size k: the best known algorithms are essentially n^{O(k)} (XP, not FPT), and a W[1]-hardness proof is strong evidence no f(k)\cdot n^{O(1)} algorithm exists. So Vertex Cover (FPT) and Clique (W[1]-hard) — near-identical-looking problems, one the complement of the other — sit on opposite sides of the tractability line. Parameterised complexity is exactly the lens that can tell them apart.

They are complementary: S is a vertex cover iff its complement is an independent set, and a clique in a graph is an independent set in the complement graph. So why the chasm? Because the parameter behaves differently. A vertex cover of size k is a small object whose choice is forced edge by edge — branching shrinks k each step. A clique of size k gives you no such local handle; finding it seems to require examining k-tuples, and the parameter refuses to detach from n's exponent. The moral: FPT-ness is a property of the problem-plus-parameter, not the raw problem — pick a different parameter and tractability can flip.

The most common beginner error is to see a running time of n^k, note that "for any fixed k this is polynomial," and declare victory. It is not FPT — it is XP, and it is usually useless. The degree of the polynomial grows with k, so the algorithm dies the moment k is more than a handful: n^{10} on a million-node graph is 10^{60} operations. FPT demands that k and n live in separate factors — f(k)\cdot n^{c} with c a constant independent of k. If you can't get k out of the exponent of n, you don't have an FPT algorithm.