Parameterized Complexity

Computational Complexity


Problem - Vertex cover:Instance - A graph G=(V,E), and a natural number kQuestion - Is there a set $W\subseteq V$, which $|W|\leqslant k$, such that for each edge $(i,j)\in E$ $$\{i,j\}\cap W\neq \varnothing$$
Problem - Independent set:Instance - A graph G=(V,E) and a natural number kQuestion - Is there a set $W\subseteq V$ with $|W|\geqslant k$, such that for each $i,j\in W$, we have $(i,j)\not\in E$

Note that, in any graph G, W is a VC iff V\W is an independent set

Similarities and differences

  • Both problems are NP complete
  • Both solvable by complete enumeration in $\mathcal{O}(n^k)$ time
  • VC can be solved in $\mathcal{O}(2^kn)$ time
  • No known $n^{o(k)}$ algorithm for IndSet
  • IndSet is (probably) harder than VC

A $\mathcal{O}(2^kn)$ algorithm for Vertex Cover

Each edge in G must be covered

Build a binary search tree of depth k as follows:

  • Pick any edge $(x,y)$ and branch
  • Left branch puts x in VC and removes it from G
  • Right branch puts y in VC and removes it from G
  • Recurse by choosing the next (any) edge on each branch

Note that:

  • If G have VC with at most k elements the algorithm must find it in one of the branches of the search tree
  • The tree has $\mathcal{O}(2^k)$ nodes, and $\mathcal{O}(n)$ work is done at each node, so $\mathcal{O}(2^kn)$ is optimal

Parameterized problems and FPT

Parameterized problem:

  • Input $I$ has distinguished integer $k$, called parameter
  • We wish to express run time in terms of both $n=|I|$ and $k$
Fixed Parameter Tractable

A parameterized problem is fixed-parameter tractable if it can be solved in time $f(k)n^c$ where f is an arbitrary function depending only on k and c is a constant (independent of k)

  • F can be arbitrarily bad
  • Any problem in P is automatically FPT
  • FPT is a robust complexity class

How (not) to choose a parameter

  • Many problems have a natural parameterization (size of required subset in a graph)
  • Some have different parametrizations, for example SAT can be parameterized by:
    • The number of variables
    • The number of clauses
    • Weight of assignment
    • Many structural parameters arising from graphs associated with a clause-set
  • If a problem X is FPT, then X with any fixed k must be in P

Examples of FPT problems

  • Finding a vertex cover of size k
  • Finding a path of length k
  • Finding k disjoint triangles
  • Drawing graph on a plane with k edge crossings
  • Finding disjoint paths that connect k pairs of vertices

FPT algorithmic techniques

  • Bounded search tree
  • Kernelization
  • Tree width
  • Graph Minors
  • Colour Coding
  • Iterative compression

Kernelization

Kernelization

A polynomial-time procedure that transforms instance $(I,k)$ into another instance $(I',k')$ - a kernel, such that

  1. $(I,k)$ is a yes-instance iff $(I',k')$ is a yes-instance
  2. $k'\leqslant k$
  3. $|I'|\leqslant f(k)$ for some function f

If a problem X admits kernelization then it is FPT. The proof for this is that the size of $(I',k')$ depends only on k, not on n, so we can solve $(I',k')$ by brute force. This is shown by point 3.

Kernelization for vertex cover

Exhaustively apply the following rules

  • Rule 1: If v is an isolated vertex, $(G,k)\Rightarrow (G\backslash v,k)$ (doesn’t touch any edges so we don’t care)
  • Rule 2: If $\operatorname{deg}(v)>k, (G,k)\Rightarrow (G\backslash v, k-1)$ (this vertex must be the cover)

Assume now neither rule can be applied

  • If $|V|>k(k+1)$ then the answer is no - each vertex v has $\deg(v)\leqslant k$, and so k vertices can cover at most $k^2$ other vertices
  • If $|V|\leqslant k(k+1)$ then we have a kernel

Kernelization and FPT

Theorem

A parameterized problem is FPT iff it admits kernelization

Proof:

  • We already know $\Leftarrow$ direction, need to prove $\Rightarrow$ direction
  • Assume the problem as a $f(k)n^c$ algorithm
    • If $f(k)\leqslant n$ when solve the problem in time $f(k)n^c\leqslant n^{c+1}$ and output yes or no instance
    • If $n\leqslant f(k)$ then we have a kernel
  • Size of the kernel is critical for the running time

Parameterized reductions

Parameterized Reduction

A parameterized reduction from problem X to problem Y is a function $\phi$ such that

  1. $\phi(I)$ is a yes-instance of Y iff I is a yes-instance of X
  2. $\phi(I)$ can be computed in time $f(k)|I|^c$ where $k$ is the parameter of I
  3. If k is the parameter f I and $k'$ is the parameter of $\phi(I)$ then $k'\leqslant g(k)$ for some function g

In this case, if Y is FPT, then so is X

The class W[1]

Problem - Short acceptance:Instance - A non-deterministic TMM, input string x, and parameter kQuestion - Is there a computation of M that accepts x after at most k steps?
W[1]

All parameterized problems that admit a parameterized reduction to Short Acceptance

  • Short acceptance is W[1]-complete by definition
  • Independent set is inter-reducible with Short Acceptance so it is also W[1] complete (parameterized reductions in both directions)
  • If independent set has a parameterized reduction to X, then X is W[1]-hard
  • It is generally believed that $FPT\neq W[1]$, but is not proven
  • Many problems are known to be W[1]-hard