fixed-parameter tractability
Many important problems are NP-hard, so no fast algorithm for ALL inputs is known. But 'hard' often hides where the hardness really lives. Take vertex cover: find a set of k vertices touching every edge of a graph. Brute force tries all subsets — hopeless. Yet in practice we often only care about SMALL covers: is there a cover of size k, where k is tiny (say 10) even though the graph is huge? Fixed-parameter tractability is the idea of isolating such a parameter k and asking for an algorithm whose blow-up is confined to k, staying efficient in the overall size n no matter how large.
Precisely, a parameterized problem is fixed-parameter tractable if it can be solved in time f(k) * n^c, where n is the input size, k is the chosen parameter, c is a constant independent of k, and f is ANY function — even an exponential like 2^k — depending only on k. The crucial point is the SEPARATION: the unavoidable exponential explosion is quarantined inside f(k) and multiplies, rather than entering the exponent of n. So if k is small, f(k) is a manageable constant and the running time is essentially polynomial in n. Compare 2^k * n (FPT, great when k is small) with n^k (NOT FPT — the exponent itself grows with k, so even k=10 on a large graph is hopeless). Vertex cover is the poster child: it has a simple 2^k * n algorithm via a bounded search tree — pick any edge, at least one endpoint must be in the cover, so branch two ways and recurse with k reduced by 1, giving a tree of depth k.
FPT matters because it gives a finer, more honest map of difficulty than 'P versus NP-hard': it explains why many NP-hard problems are routinely solved in practice — their hard instances need a large parameter, which real instances often lack. Treewidth, solution size, and number of clusters are common parameters. The honest caveats: f(k) can be astronomically large (2^(2^k) is still 'FPT' but useless), so FPT is a theoretical efficiency class, not a promise of speed; not every parameterized problem is FPT (the W-hierarchy classifies likely-not-FPT problems such as finding a k-clique, believed to require roughly n^k); and the win depends entirely on the parameter actually being small.
Vertex cover of size k via a bounded search tree: take any edge (u,v); the cover must contain u or v. Branch into two cases — put u in (recurse on the graph minus u, with k-1) or put v in — each shrinking k by 1. The recursion tree has depth k and branching 2, so it explores at most 2^k leaves; total time 2^k * (graph size). That is f(k)*n with f(k)=2^k: textbook FPT.
FPT: time f(k)*n^c — the explosion is confined to f(k), separate from the exponent of n.
FPT separates the blow-up: f(k)*n^c (good) versus n^k (not FPT — k is IN the exponent). But f(k) may be huge (2^(2^k) is still 'FPT'), so FPT is a complexity class, not a guarantee of practical speed. Some problems (e.g. k-clique) are believed NOT to be FPT — that is what the W-hierarchy formalizes.