Symptom

Your problem is NP-hard, and yet it keeps being easy.

You are computing a minimum vertex cover to select monitoring points in a network. Twelve thousand nodes. NP-hard, per T028, so you brace for the worst — and the answer comes back in under a second, every time. The cover is small, around thirty nodes, because the network is sparse and the interesting nodes are few.

Then your colleague’s instance, on a graph a tenth the size, runs for hours.

“NP-hard” is not distinguishing between these two cases, and something clearly is. The classification you were taught puts them in the same box. Something about the shape of the instance, not its size, decides which world you are in, and the theory that names that something is the most practically useful refinement of NP-hardness available.

Statement

A parameterized problem takes an instance of size $n$ and a parameter $k$. It is fixed-parameter tractable (FPT) if it is solvable in time

$$f(k) \cdot n^{O(1)}$$

for some computable $f$. The exponential blowup is confined to $k$, and the dependence on $n$ is polynomial with a degree that does not grow with $k$.

Compare $n^{O(k)}$, which is the naive brute-force shape (class XP). The distinction is everything. Vertex cover with $k = 20$ on a million-node graph: brute force over all $\binom{n}{k}$ subsets is about $10^{102}$ operations, while the FPT algorithm at $1.2738^k \cdot n$ is about 127 million — a second’s work. Same problem, same instance, opposite outcomes.

Vertex cover is FPT, in $O(1.2738^k + kn)$.

Clique is not, apparently. Clique parameterized by size is W[1]-complete, and W[1] $\ne$ FPT is the field’s working hypothesis, standing in the same role as P $\ne$ NP. It follows from the Exponential Time Hypothesis, so the two beliefs are linked.

So NP-hardness splits. Some NP-hard problems collapse to easy when a parameter is small, and others do not, and which is which is not visible from the NP-hardness proof.

Argument

Vertex cover is FPT, by bounded search tree. Pick any edge $(u,v)$. Any cover contains $u$ or $v$ — no third option. Branch: recurse having taken $u$ with budget $k-1$, and recurse having taken $v$ with budget $k-1$. Depth $k$, branching factor 2, so at most $2^k$ leaves, each doing $O(n)$ work. That gives $O(2^k n)$ immediately, and refinements on high-degree vertices reduce the base to 1.2738.

The key is that the branching is on a bounded local choice, and the budget strictly decreases. The instance size is irrelevant to the recursion depth. That is the FPT pattern in one sentence.

Kernelization, which is the technique you will actually deploy. Preprocess in polynomial time until what remains has size bounded by a function of $k$ alone. For vertex cover, two rules (Buss):

  • Any vertex of degree greater than $k$ must be in the cover. Otherwise all its neighbours are, exceeding the budget. Take it, decrement $k$.
  • Delete isolated vertices; they are irrelevant.

After exhaustive application, every remaining vertex has degree at most $k$, and $k$ vertices of degree $\le k$ cover at most $k^2$ edges. If more edges remain, answer no. The instance is now $O(k^2)$ regardless of whether it started with a million vertices. Solve the kernel by brute force if you like.

Kernelization is a theorem about preprocessing — a provable guarantee about how much a polynomial-time cleanup pass can shrink an instance. That is unusual and valuable: it turns “run some reduction rules first” from folklore into something with a bound attached. And a problem is FPT if and only if it is kernelizable, which is a genuinely surprising equivalence.

Colour coding, for finding small patterns. To find a path of length $k$, randomly colour vertices with $k$ colours. If a $k$-path exists, it is colourful — all distinct colours — with probability $k!/k^k \ge e^{-k}$. Colourful paths are findable by dynamic programming over colour subsets in $O(2^k \cdot \text{poly})$. Repeat $e^k$ times for high probability. Total $O((2e)^k \cdot \text{poly})$: FPT. Randomization converts a global search into a local one, and the technique derandomizes with perfect hash families.

W[1]-hardness, and why clique resists. The W-hierarchy is defined by weighted circuit satisfiability at increasing depths, and it is layered:

$$\text{FPT} \subseteq \text{W}[1] \subseteq \text{W}[2] \subseteq \cdots \subseteq \text{XP}$$

Clique and independent set are W[1]-complete; dominating set is W[2]-complete. Hardness is shown by FPT reductions, which must run in FPT time and bound the new parameter by a function of the old — ordinary Karp reductions are useless here, since they routinely blow the parameter up. Rebuilding the reduction catalogue under this stricter notion is exactly what the field did, mirroring what T031 did for approximation.

Under ETH (no $2^{o(n)}$ algorithm for 3-SAT), clique requires $n^{\Omega(k)}$, so the brute-force exponent is essentially right. W[1]-hardness is a real barrier, not an absence of ideas.

Choosing the parameter is the actual skill. Solution size is the obvious choice and often the wrong one. Treewidth is frequently better: most NP-hard graph problems are FPT in treewidth by Courcelle’s theorem, and real networks — control-flow graphs, road networks, dependency graphs — often have small treewidth. Other useful parameters are the number of distinct values, the maximum degree, the distance from a tractable class, and the solution’s structural depth. The same problem is FPT under one parameter and W[1]-hard under another, so “is it FPT” is not a well-posed question until you say parameterized by what.

Forbids

FPT algorithms for W[1]-hard problems, unless FPT = W[1]. Clique, independent set and dominating set parameterized by solution size. The $n^{O(k)}$ brute force is essentially optimal.

Polynomial kernels for problems without them. Some FPT problems provably have no polynomial kernel unless the polynomial hierarchy collapses — $k$-path is the standard example. So there are problems that are FPT and yet cannot be preprocessed down to polynomial size, which is a genuinely non-obvious separation.

Reading tractability off NP-hardness. Vertex cover and clique are both NP-complete and are complements of each other on the same graph, yet one is FPT and the other is W[1]-hard. The classical theory cannot see this at all.

Karp reductions transferring parameterized hardness. They do not preserve parameters. Every parameterized hardness result needs its own FPT reduction.

Does not forbid

It does not mean W[1]-hard problems are unsolvable in practice. Cliquer and modern maximum-clique solvers handle graphs with thousands of vertices routinely, and clique enumeration is standard in bioinformatics on real protein-interaction networks. W[1]-hardness is worst-case over all instances and all parameter values.

It does not mean FPT means fast. Courcelle’s theorem gives FPT algorithms in treewidth for a huge class of problems, with $f(k)$ a tower of exponentials — completely unimplementable. The Robertson–Seymour graph-minor machinery gives FPT algorithms with constants that have been described, accurately, as galactic. FPT is a classification, and $f(k)$ is the thing you must actually look at.

It does not mean parameterization is only theoretical. SAT solvers exploit backdoor sets, which is a parameterized idea. Kernelization rules are what every good ILP presolver does — Gurobi’s presolve is kernelization without the theorems. Treewidth-based inference is how probabilistic graphical models are solved, junction trees being exactly the treewidth algorithm.

It does not require you to compute the parameter first. Many FPT algorithms work by iterative deepening on $k$, and treewidth has good FPT approximations. You do not need to know the parameter’s value in advance to benefit.

It does not conflict with approximation. They compose: parameterized approximation gives $(1+\epsilon)$ answers in $f(k, \epsilon) \cdot n^{O(1)}$, and some problems hard under either relaxation alone yield to both together. Recent parameterized-inapproximability results (T031) map where even that fails.

Boundary

  • Treewidth is the parameter that pays off most often. Courcelle’s theorem makes every property expressible in monadic second-order logic FPT in treewidth, which covers most graph problems you will meet. The catch is $f(k)$.
  • Above-guarantee parameterization. MAX-SAT is trivially half-satisfiable, so parameterize by how far above $m/2$ you want to go. Parameterizing by the interesting part of the answer rather than its magnitude is often what makes a problem tractable.
  • Kernel lower bounds. The composition framework proves no polynomial kernel exists for specific problems unless coNP $\subseteq$ NP/poly. Preprocessing has its own barrier theory, which is a nice parallel to T030.
  • ETH and SETH give finer bounds. Beyond W-hardness, ETH gives statements like “no $2^{o(k)}$ algorithm for vertex cover” and SETH gives conditional lower bounds on polynomial-time problems too — edit distance in $O(n^{2 - \epsilon})$ is ruled out under SETH. That is fine-grained complexity, and it applies to problems already in P.
  • The practical reading. When you hit an NP-hard problem, ask what is small about your instances before asking for a heuristic. Solution size, treewidth, degree, number of distinct values, distance from a tractable class. If something is small and the problem is FPT in it, you get an exact answer quickly, which is strictly better than the approximation you were about to settle for.