Parameterized Complexity and Kernelization

Measure difficulty in terms of the input size $n$ and a separate parameter $k$ — typically the solution size, a structural width, or a bound in the statement.

FPT — fixed-parameter tractable

A problem is FPT if it is solvable in

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

for some function $f$. The exponential blowup is confined to $k$, so the algorithm is practical whenever $k$ is small — regardless of how large $n$ is.

Contrast: $O(n^k)$ is not FPT (the exponent depends on $k$); it is the weaker class XP.

Complexity	Class	$n=10^5$, $k=10$
$2^{k}n$	FPT	$10^8$ ✔
$1.28^k+kn$	FPT	$10^6$ ✔
$k!n$	FPT	$3.6\cdot 10^{11}$ ✘ (but FPT)
$n^k$	XP	astronomically large ✘

The FPT problems

Problem	Parameter	Best known
Vertex cover	solution size $k$	$O(1.28^k+kn)$
Feedback vertex set	$k$	$O(3.46^{k}n)$
$k$-path (a path of $k$ vertices)	$k$	$O(2^k\mathrm{poly})$ (colour coding)
Steiner tree	number of terminals	$O(3^{k}n+2^k{n}^2)$
TSP	number of cities	$O(2^n{n}^2)$
Anything on bounded treewidth	treewidth $w$	$2^{O(w)}n$
Closest string	number of strings	FPT
$d$-hitting set	$k$	$O(d^{k}n)$

The W-hierarchy — what is not FPT

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

Problem	Class
Independent set / clique (parameter = size)	W[1]-hard
Dominating set	W[2]-hard
Set cover (parameter = number of sets)	W[2]-hard
Graph colouring (parameter = colours)	not FPT (NP-hard for $k=3$)

W[1]-hardness is the parameterized analogue of NP-hardness: no FPT algorithm is expected. Note the striking asymmetry — vertex cover is FPT, but its complement independent set is W[1]-hard.

Kernelization — the defining technique

Reduce the instance in polynomial time to an equivalent one whose size depends only on $k$ (the kernel), then solve the kernel by brute force.

Vertex cover kernel — Buss’s rules

1. A vertex of degree $>k$ must be in the cover (else all its neighbours are, exceeding $k$): take it, decrement $k$.
2. Delete isolated vertices.
3. If more than $k^2$ edges remain, answer no (each of $k$ vertices covers $\le k$ edges).

The result is a kernel with $O(k^2)$ edges and $O(k^2)$ vertices. The Nemhauser-Trotter LP gives a stronger $2k$-vertex kernel.

// after kernelization, branch: for an uncovered edge (u,v),
// either u or v is in the cover -> O(2^k) branching, or O(1.28^k) with better rules
bool vc(Graph& g, int k) {
    kernelize(g, k);
    if (g.edges.empty()) return true;
    if (k == 0) return false;
    auto [u, v] = g.anyEdge();
    return vc(g.remove(u), k - 1) || vc(g.remove(v), k - 1);
}

A problem is FPT iff it has a kernel. That equivalence is the central theorem of the field.

Bounded treewidth

Treewidth measures how tree-like a graph is: trees have $w=1$, series-parallel graphs $w=2$, planar graphs $O(\sqrt{n})$, and complete graphs $n-1$.

Almost every NP-hard graph problem is solvable in $2^{O(w)}n$ on graphs of treewidth $w$ (Courcelle’s theorem, for anything expressible in monadic second-order logic).

This is why so many problems are easy on trees — treewidth 1. In contests, “the graph is a tree” or “the graph is a cactus” is exactly this escape hatch.

Structure	Treewidth
Tree, forest	1
Cycle, cactus	2
Series-parallel	2
Outerplanar	2
$k\times n$ grid	$\min (k,n)$
Planar	$O(\sqrt{n})$
Complete graph	$n-1$

Colour coding

A randomised FPT technique: to find a path of $k$ vertices, colour the vertices randomly with $k$ colours and look for a colourful path (all colours distinct) — which is a $O(2^k)$ DP over colour subsets. The true path is colourful with probability $k!/k^k\approx e^{-k}$, so $O(e^k)$ repetitions suffice.

$O((2e{)}^k\mathrm{poly})$, derandomisable with $k$-perfect hash families. The same idea finds any small subgraph pattern.

In competitive programming

Parameterized thinking is really “read the constraints”:

Constraint	Intended technique
$n\le 20$	$2^n$ DP
$n\le 40$	meet in the middle
$k\le 15$ terminals, $n$ large	Steiner tree DP
$k\le 20$ special vertices	subset DP over those
”The graph is a tree”	tree DP (treewidth 1)
“The graph is a cactus”	treewidth 2
”At most $k$ removals”	branching, $O(c^k)$
A small alphabet or value range	that is the parameter

Two independent small numbers in the constraints ($n$ large, $k$ tiny) is the signature of an FPT problem — and the exponential factor is meant to be in $k$.

See also: NP-Completeness · Tree DP · Branch and Bound