Parameterized Complexity, in depth: FPT versus XP, kernels, bounded search trees, colour coding, treewidth and W[1]-hardness

Why one number is the wrong ruler

Consider vertex cover: find at most k vertices touching every edge of a graph with n vertices. Trying every subset of size k costs about n**k steps. A bounded search tree costs about 2**k * n. For n = 1,000,000 and k = 30 the first is 10**180 and hopeless; the second is about 10**15, heavy but feasible, and with kernels and better branching it drops by many orders of magnitude. Both are exponential, but only one puts the exponent somewhere harmless.

That difference, k in the exponent of n versus k only in a separate factor, is the whole subject. It also explains a puzzle: independent set asks for at least k pairwise non-adjacent vertices, and a set is independent exactly when its complement is a vertex cover, yet the two behave completely differently when k is small. The complement of a small independent set is a huge cover, so the cheap parameter for one is the expensive one for the other.

FPT, XP and kernels

A parameterized problem is a decision problem whose instances are pairs (x, k). It is fixed-parameter tractable (FPT) if some algorithm decides it in time f(k) * |x|**c for a computable function f and a constant c that does not depend on k. It is in XP if it can be decided in time |x|**g(k), polynomial for each fixed k but with a degree that grows with it. Every FPT problem is in XP; the interesting question is the reverse.

A kernelization is a polynomial-time procedure that turns (x, k) into an equivalent (x', k') with both |x'| and k' bounded by some g(k). A basic theorem says that a decidable problem is FPT exactly when it has a kernel: given a kernel, solve the small instance by brute force; given an FPT algorithm, either |x| is large compared with f(k) and the algorithm runs in polynomial time anyway, or the input is already small. The practical interest is in kernels whose size g(k) is polynomial, ideally linear.

Kernelization in practice

Kernels come from reduction rules, each provably safe, applied until none fires. Buss's rules for vertex cover are the canonical example. Rule 1: delete isolated vertices. Rule 2: a vertex of degree greater than k must be in every cover of size at most k (otherwise all its more than k neighbours would be), so take it and decrease k. When neither applies, every vertex has degree at most k, so k cover vertices touch at most k*k edges. A remaining graph with more edges is a no-instance, and otherwise it has at most k*k edges and 2*k*k non-isolated vertices: a quadratic kernel computed in linear time.

Stronger kernels use linear programming. Solve the LP relaxation of vertex cover; the Nemhauser-Trotter theorem says an optimal half-integral solution exists in which vertices at value 1 can be taken, vertices at 0 discarded, and only those at 1/2 remain, at most 2k of them for a yes-instance. Crown reductions reach a similar linear bound combinatorially. The vertex cover page shows the related approximation algorithms; here the point is that a kernel is a preprocessing step you can add to any exact solver, including an ILP or SAT solver, and it often removes most of the input.

Bounded search trees

A bounded search tree picks a small structure that any solution must hit and branches on how. For vertex cover, every edge uv forces u or v, giving two branches each reducing k by one: at most 2**k leaves. Branching on a vertex v is better: either v is in the cover, or all its neighbours are. On a vertex of degree at least 3 the second branch reduces k by at least 3, and the recurrence T(k) = T(k-1) + T(k-3) solves to about 1.47**k. Careful case analysis has pushed vertex cover to 1.2738**k (Chen, Kanj and Xia, 2010). Here is a compact solver combining Buss rules with degree branching:

def remove(adj, vs):
    """Delete vertex set vs; drop vertices left with no edges."""
    out = {u: nb - vs for u, nb in adj.items() if u not in vs}
    return {u: nb for u, nb in out.items() if nb}

def vertex_cover(adj, k):
    """adj: dict vertex -> set of neighbours. Return a cover of size <= k, or None."""
    if k < 0:
        return None
    if not adj:
        return set()
    for u, nb in adj.items():                 # degree-1 rule: take the neighbour
        if len(nb) == 1:
            (w,) = nb
            sub = vertex_cover(remove(adj, {w}), k - 1)
            return None if sub is None else sub | {w}
    v = max(adj, key=lambda u: len(adj[u]))
    if len(adj[v]) > k:                       # Buss rule 2: v is forced
        sub = vertex_cover(remove(adj, {v}), k - 1)
        return None if sub is None else sub | {v}
    if sum(map(len, adj.values())) // 2 > k * k:   # Buss bound: no-instance
        return None
    sub = vertex_cover(remove(adj, {v}), k - 1)    # branch A: take v
    if sub is not None:
        return sub | {v}
    nv = set(adj[v])                               # branch B: take N(v)
    sub = vertex_cover(remove(adj, nv), k - len(nv))
    return None if sub is None else sub | nv

Re-applying the rules at every node of the tree, not just once at the root, is what makes such solvers fast in practice: branching creates new low-degree vertices that the rules then clear for free.

Worked example

Take a star with centre c and ten leaves, plus a separate triangle x, y, z, and ask for a cover with k = 3. No vertex has degree 1 in the triangle, but every leaf has degree 1, so the degree-1 rule takes c and k becomes 2; the leaves are now isolated and vanish. The triangle remains: three edges, which is at most k*k = 4, so no rejection. Branch A takes x with k = 1, leaving the edge yz; the degree-1 rule takes one endpoint and k reaches 0 with no edges left. The answer is {c, x, z} (or an equivalent), found after exploring a single path of the tree. Brute force over all 3-subsets of 14 vertices would have tried up to 364 candidates. On real graphs with millions of low-degree vertices, the rules routinely do almost all of the work.

Colour coding

Some problems resist branching. Finding a simple path on k vertices is one: a search must remember which vertices it used, which is n-dependent. Colour coding (Alon, Yuster and Zwick, 1995) fixes this with randomness. Colour the vertices uniformly with k colours and look only for a colourful path, one whose vertices all have different colours; that only needs to remember the set of colours used, 2**k possibilities. A fixed k-path is colourful with probability k!/k**k, which exceeds e**-k, so about e**k random colourings find it with constant probability.

import math, random

def colourful_path_exists(adj, k, colour):
    # masks[v]: colour sets of colourful paths ending at v with current length
    masks = {v: {1 << colour[v]} for v in adj}
    for _ in range(k - 1):
        nxt = {v: set() for v in adj}
        for u, ms in masks.items():
            for m in ms:
                for w in adj[u]:
                    bit = 1 << colour[w]
                    if not m & bit:
                        nxt[w].add(m | bit)
        masks = nxt
    return any(masks.values())

def has_k_path(adj, k, rounds=3):
    trials = int(rounds * math.e ** k) + 1     # failure probability <= e**-rounds
    for _ in range(trials):
        colour = {v: random.randrange(k) for v in adj}
        if colourful_path_exists(adj, k, colour):
            return True                         # never a false positive
    return False

The error is one-sided: a yes answer is always right. Deterministic versions replace random colourings with hash families, and algebraic methods improve the base of the exponent further.

Iterative compression and treewidth

Iterative compression builds a solution incrementally. Add vertices one at a time; at each step you hold a solution of size k + 1 for the current graph and need one of size k. Guess which part of the old solution survives (at most 2**(k+1) guesses) and solve the much more constrained compression problem. It gave the first FPT algorithm for odd cycle transversal (Reed, Smith and Vetta, 2004) and is central for feedback vertex set.

Treewidth measures how tree-like a graph is. Given a tree decomposition of width w, independent set, colouring, dominating set and many others fall to dynamic programming over bags in time like 2**w * n or 3**w * n, the same idea as subset dynamic programming applied bag by bag. Courcelle's theorem says every property expressible in monadic second-order logic is decidable in linear time on graphs of bounded treewidth, a sweeping classification result whose hidden constants are far too large to run directly. Treewidth is a structural parameter: it is small on road networks, circuits and many program control-flow graphs whatever the solution size is.

Hardness: W[1], ETH and kernel lower bounds

When no FPT algorithm appears, hardness theory says whether to keep looking. Parameterized reductions map (x, k) to (x', k') in f(k) * poly(|x|) time with k' bounded by a function of k. The W-hierarchy classifies problems under them. Clique and independent set are W[1]-complete, dominating set is W[2]-complete, and FPT = W[1] is considered as unlikely as P = NP. The clique reduction page shows the classical side of that hardness.

Fine-grained lower bounds come from the Exponential Time Hypothesis (ETH): 3-SAT on n variables has no 2**o(n) algorithm. Under ETH, vertex cover has no 2**o(k) * poly(n) algorithm, so the single-exponential bound is the right shape, and k-clique has no f(k) * n**o(k) algorithm, so brute force over k-subsets is essentially optimal. Kernel lower bounds are a third tool: k-path is FPT but has no polynomial kernel unless NP is contained in coNP/poly, so do not spend effort hunting for one.

Engineering a parameterized solver

Choosing the parameter is the main design decision, and it should come from data. Measure the distribution of candidate parameters on production instances: solution size, maximum degree, treewidth (computed heuristically with min-degree or min-fill orderings), number of distinct labels. Pick the one that stays small on the instances that matter. Structural parameters often beat solution size, because the solution may be large while the structure is simple.

Operationally, treat a parameterized solver like any exponential component. Run reductions first and log the kernel size, which predicts runtime better than input size. Put a node or time budget on the search and fall back to an approximation or heuristic answer when it trips, reporting which one was returned. Iterate on k upward from a lower bound (for vertex cover, the size of any maximal matching) rather than guessing large. Kernels also combine well with general solvers: shrink first, then hand the kernel to ILP or SAT.

Failure modes

• The parameter is not small in practice. 1.27**k is fine at k = 60 and hopeless at k = 400; measure before building.
• Unsafe reduction rules. A rule that is right only for connected graphs, or that forgets to decrease k, silently returns wrong answers. Test every rule against brute force on small random instances.
• Rules applied once. Skipping re-application inside the search tree throws away most of the speed.
• Confusing FPT with XP. An n**k algorithm is polynomial for fixed k and still useless at scale.
• Trusting galactic theorems. Courcelle-style results classify; they do not ship.
• Recursion depth. Deep search trees in Python hit the recursion limit; use an explicit stack in production.

Trade-offs

Parameterized algorithms give exact answers with guarantees tied to a quantity you can measure, but only when that quantity is small, and they take more design work than plugging the problem into a general solver. Approximation algorithms give fast answers with bounded error for any parameter value. Generic ILP and SAT solvers are robust and often surprisingly good, with no guarantee you can explain. The strongest systems mix them: kernelize, try the FPT search under a budget, and fall back to approximation, keeping the kernel because it helps every downstream method.

What to do next

1. Pick one NP-hard problem in your codebase and list three candidate parameters.
2. Measure their distribution on real instances; keep the ones whose 95th percentile is small.
3. Write and brute-force-test the safe reduction rules first, and log kernel sizes.
4. Add a bounded search tree with a node budget and an approximation fallback.
5. If the problem looks W[1]-hard for every parameter you can find, stop and use heuristics or approximation instead.
6. Read about tree decompositions next; structural parameters often unlock problems where solution size does not.