64 Fixed parameter tractable (FPT) Algorithm

• Recall that in (classical) Vertex Cover Problem, the goal is to find a minimum vertex cover
• In the parameterised Vertex Cover problem, given a parameter $k$, we only want to know if $G$ has a vertex cover of size $\le k$ or not
• The goal is to develop a fast algorithm when $k$ is small, even if the input size $n$ is large

Definition

A parameterised problem with parameter $k$ and input size $n$ is said to be fixed parameter tractable (FPT) if it can be solved in $f(k)\cdot n^{O(1)}$ time, for some function $f$.

The Parameterised Vertex Cover Problem

The

Given an undirected graph $G=(V,E)$ on $n$ vertices and a prameter $k$, is there a set $X\subseteq V$ of size $\le k$ such that each edge of $G$ has at least one end-point in $X$.

The Minimum Vertex Cover problem can be solved by $O(n)$ calls to the $k$-VC problem

• Check if there is a $k$-VC for $k=0$
• Check if there is a $k$-VC for $k=1$
• Check if there is a $k$-VC for $k=2$
• $\cdots$
• $\cdots$
• Check if there is a $k$-VC for $k=n-1$

Consequences

• Assuming $\mathrm{P}\ne \mathrm{NP}$, we cannot expect an algorithm for the $k$-VC problem which runs in time which is polynomial in both $k$ and $n$

Depth Search Tree

Correctness of the algorithm

• If at least one of the graphs at the leaf nodes has no edges, then there is a vertex cover of size $\le k$
• Otherwise, there is no vertex cover of size $\le k$

Analysis of the running time

• Search tree is a binary tree of height $k\Rightarrow$ there are $2^k$ leaf nodes
• Total time spent at each vertex is $n^{O(1)}$

Not all problems have FPT algorithms!