A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Parameterized complexity refines the NP-hardness classification by asking: is a problem solvable in time f(k) * n^O(1), where k is a parameter of the input (not the input size)? Problems solvable in this form are Fixed-Parameter Tractable (FPT). Vertex cover parameterized by solution size k is FPT: solvable in O(2k * n) time via bounded search trees. Treewidth is a structural parameter that measures how "tree-like" a graph is — many NP-hard problems (independent set, coloring, Hamiltonian cycle) become FPT when parameterized by treewidth, solvable in time f(tw) * n via dynamic programming on tree decompositions. Kernelization provides a complementary approach: reducing the instance to an equivalent instance of size bounded by g(k), independent of n. The W-hierarchy (W[1], W[2], ...) classifies parameterized problems believed not to be FPT, analogous to the polynomial hierarchy for classical complexity.
NP-hardness is a blunt instrument: it says that no polynomial-time algorithm solves all instances, but says nothing about which instances are hard. Parameterized complexity provides a finer lens. Instead of measuring complexity solely as a function of input size n, it measures complexity as f(k) * nc, where k is a problem-specific parameter and f can be any computable function. If c is a constant (independent of k), the problem is Fixed-Parameter Tractable (FPT) — the combinatorial explosion is confined to the parameter, and for small k the algorithm is efficient.
Vertex cover is the poster child. The bounded search tree algorithm picks any edge (u,v), branches on whether u or v is in the cover (one must be), and recurses with k decremented. The recursion depth is k, branching factor is 2, and each step does O(n) work: total O(2k * n). For k = 30 in a graph with a million vertices, this is about 1015 — feasible with a fast computer. The same problem solved by brute-force enumeration of size-30 subsets would require C(106, 30) operations — a number with 160 digits. FPT algorithms exploit problem structure (here, the constraint that cover vertices must hit every edge) to confine the exponential search to the parameter.
Treewidth provides a structural approach to parameterized tractability. A tree decomposition breaks a graph into overlapping "bags" arranged in a tree structure, with the constraint that each edge appears in some bag and each vertex's bags form a connected subtree. The treewidth — maximum bag size minus 1 — measures the graph's departure from tree-likeness. On trees (treewidth 1), many problems are solvable by straightforward DP. On graphs of bounded treewidth w, the same DP works but with state space exponential in w instead of n. Courcelle's meta-theorem makes this precise: any property definable in monadic second-order logic is decidable in f(w) * n time on graphs of treewidth w.
Kernelization complements FPT algorithms by reducing instances to equivalent smaller ones. A kernelization algorithm runs in polynomial time and produces an instance with size bounded by g(k) — independent of n — that has a solution if and only if the original does. For vertex cover, kernelization reduces to at most 2k vertices. This is powerful in practice: a huge graph with a small vertex cover parameter can be reduced to a tiny equivalent instance. The theory of kernelization lower bounds, using cross-composition and polynomial parameter transformations, proves that certain problems cannot have small kernels under complexity assumptions, providing a fine-grained map of which problems compress and which do not.