Parameterized Algorithms

Overview

Parameterized complexity provides a framework for tackling NP-hard problems by isolating the combinatorial explosion to a parameter k, which is often small in practice. An algorithm with runtime f(k) * poly(n) is fixed-parameter tractable (FPT) — polynomial for any fixed k, with the exponential dependence confined to k alone.

Fixed-Parameter Tractability (FPT)

A parameterized problem is in FPT if it can be solved in time f(k) * n^O(1), where f is any computable function of k alone and n is the input size.

Examples

| Problem | Parameter k | FPT Runtime | |-------------------|---------------------|--------------------------| | Vertex Cover | Solution size | O(1.2738^k + kn) | | k-Path | Path length | O(2^k * n^2) | | Feedback Vertex Set | Solution size | O(3.619^k * n^2) | | Treewidth | Treewidth | O(2^O(k^3) * n) | | k-Clique | Clique size | W[1]-hard (unlikely FPT) |

Kernelization

Preprocessing: reduce the instance to an equivalent smaller instance (kernel) whose size depends only on k. If the kernel size is polynomial in k, the problem is FPT.

Vertex Cover Kernelization

Crown reduction and LP-based kernel:

Solve LP relaxation of vertex cover
Remove vertices with x_v = 0 (not in cover) and x_v = 1 (in cover, reduce k)
Remaining instance has at most 2k vertices (Nemhauser-Trotter theorem)

Result: O(k^2) edge kernel, reducible to 2k vertex kernel.

Kernelization Examples

| Problem | Parameter | Kernel Size | |----------------------|-----------|------------------| | Vertex Cover | k | 2k vertices | | Feedback Vertex Set | k | O(k^2) vertices | | k-Path | k | O(k) vertices | | Dominating Set (planar)| k | O(k) vertices | | Point Line Cover | k | O(k^2) points |

Lower Bounds on Kernel Size

Under reasonable complexity assumptions (NP not in coNP/poly):
No polynomial kernel for k-Path in general graphs
No polynomial kernel for OR-composition problems (e.g., k-coloring parameterized by k)

Bounded Search Tree

Systematically explore all possibilities by branching on local structure.

Vertex Cover by Branching

VertexCover(G, k):
    if k < 0: return NO
    if E = empty: return YES (empty cover)
    pick any edge (u, v)
    return VertexCover(G - u, k - 1) OR VertexCover(G - v, k - 1)

Branching factor: 2 (include u or v)
Depth: at most k
Time: O(2^k * n) — simple but effective

Improved Branching

Branch on vertex of max degree d: branching vector (1, d) gives base < 2
Current best for vertex cover: O(1.2738^k * kn) [Chen-Kanj-Xia]

Branching Vectors and Recurrences

Branch (a, b): T(k) = T(k-a) + T(k-b)
Solve characteristic equation: x^max(a,b) = x^(max(a,b)-a) + x^(max(a,b)-b)
Largest root determines the base of the exponential

Iterative Compression

Technique for problems where we can efficiently solve a "compression" step.

Framework

Order vertices v_1, ..., v_n
Maintain a solution for the subgraph induced by {v_1, ..., v_i}
When adding v_{i+1}, we have a solution of size k+1; compress to size k

Feedback Vertex Set by Iterative Compression

Compression step: given FVS S of size k+1, find FVS S' of size k (or prove none exists).

For each subset X of S (at most 2^(k+1) choices):
- Assume S' intersect S = S \ X
- Check if remaining graph minus (S \ X) has a FVS of size |X| - 1 avoiding S \ X (reduces to a simpler problem)
Total: O(2^k * k * n^2) per step, O(n) steps, giving O(2^k * k * n^3)

Applications

Odd Cycle Transversal
Directed Feedback Vertex Set
Edge Bipartization

Color Coding

Technique for finding substructures of size k (paths, trees, subgraphs).

k-Path Detection

Randomly color each vertex with one of k colors
Find a colorful k-path (all vertices have distinct colors) via DP
Repeat O(e^k) times (probability of colorful path = k!/k^k >= e^{-k})

DP for colorful path:

For each subset S of colors, vertex v:
    colorful_path[S][v] = true if there is a path using exactly colors S ending at v
Base: colorful_path[{c(v)}][v] = true for all v
Transition: colorful_path[S][v] = OR over neighbors u of v:
    colorful_path[S \ {c(v)}][u] and c(v) in S and c(v) != c(u)

DP time: O(2^k * n * m)
Total: O(2^k * e^k * nm) = O((2e)^k * nm) randomized
Derandomize via perfect hash families: O(2^k * k^O(1) * nm * log n)

Treewidth

Measures how "tree-like" a graph is. Many NP-hard problems become FPT parameterized by treewidth.

Definition

A tree decomposition of G = (V, E) is a tree T where:

Each node of T has a bag B_i, a subset of V
Every vertex v appears in at least one bag
For every edge (u,v), some bag contains both u and v
For every vertex v, the bags containing v form a connected subtree of T

Width = max bag size - 1. Treewidth tw(G) = minimum width over all tree decompositions.

Examples

Trees have treewidth 1
Series-parallel graphs: treewidth <= 2
Outerplanar graphs: treewidth <= 2
k x k grid: treewidth = k
Planar graphs: treewidth O(sqrt(n))
Complete graph K_n: treewidth n - 1

Computing Treewidth

Exact: NP-hard in general, but FPT: O(2^O(k^3) * n) for treewidth k
Constant-factor approximation in O(2^O(k) * n) time [Bodlaender et al.]
5-approximation in O(2^O(k) * n) [Bodlaender-Drange-Dregi-Fomin-Lokshtanov-Pilipczuk 2016]

DP on Tree Decompositions

Once a tree decomposition of width k is found, solve problems by DP on the tree.

Framework

For each bag, enumerate all possible partial solutions restricted to the bag. Combine using the tree structure (introduce/forget/join nodes in nice tree decomposition).

Typical Runtimes

Independent Set: O(2^k * n)
Vertex Cover: O(2^k * n)
Graph Coloring (q colors): O(q^k * n)
Hamiltonian Path: O(k! * 2^k * n) (but O(2^k * n) via rank-based approach)
Steiner Tree: O(3^k * n)

Courcelle's Theorem

Every graph property expressible in monadic second-order logic (MSO2) can be decided in linear time on graphs of bounded treewidth.

MSO2: quantify over vertices, edges, vertex sets, and edge sets
Expressible properties: 3-colorability, Hamiltonicity, dominating set existence
Runtime: f(k, |phi|) * n where f is typically a tower of exponentials
Theoretically powerful but often impractical due to enormous constants

MSO2 Examples

k-coloring: "there exist sets S_1, ..., S_k partitioning V such that no edge has both endpoints in the same S_i"
Hamiltonian cycle: "there exists an edge set F such that every vertex is incident to exactly two edges in F and the subgraph (V, F) is connected"

W-Hierarchy

Classification of parameterized problems that are believed NOT to be FPT.

Hierarchy

FPT subset W[1] subset W[2] subset ... subset XP

W[1]: complete problem is k-Clique. Parameterized reduction from k-Clique.
W[2]: complete problem is k-Dominating Set.
W[t]: defined via bounded-depth circuits
Conjecture: FPT != W[1] (analogous to P != NP)

W[1]-Hard Problems

k-Clique
k-Independent Set
k-Multicolored Clique
Longest Path (when not parameterized correctly)

W[2]-Hard Problems

k-Dominating Set (general graphs)
k-Set Cover

Reductions

Parameterized reductions must:

Run in FPT time
Map YES instances to YES instances
Map the parameter k to k' = g(k) (independent of n)

Additional Techniques

Randomized FPT Algorithms

Random separation: partition vertices randomly, solve structured subproblem
Algebraic techniques: evaluate multilinear monomials (Koutis-Williams O(2^k * poly(n)))

Important Width Parameters

Pathwidth: treewidth restricted to path decompositions
Cliquewidth: generalizes treewidth, captures dense graphs
Treedepth: minimum height of elimination tree

Bidimensionality

For planar and H-minor-free graphs
If OPT >= k implies treewidth is Omega(sqrt(k)):
- Subexponential FPT: O(2^O(sqrt(k)) * n)
- Applies to: vertex cover, dominating set, feedback vertex set on planar graphs

Summary

Parameterized algorithms provide practical solutions to NP-hard problems when a natural parameter is small. Kernelization reduces instance size as preprocessing. Branching, color coding, and iterative compression are key algorithm design techniques. Treewidth-based DP is a universal tool for tree-like structures. The W-hierarchy classifies the hardness landscape of parameterized problems.