# Reduction from Vertex Cover to an Independent Set problem

Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim that independent set can also be solved in time polynomial in terms of $n$ and exponential in terms of $k$ ? ($k$ here stands for the minimum size of an independent set)

• my intuition dictates that the answer is yes because vertex cover and independent set are essentially the same problem and the minimum set size and minimum vertices numbers are closely related. Can anyone confirm ? – 372 May 8 '13 at 23:41

No. The typical reduction from Independent Set to Vertex Cover doesn't preserve the parameter ($k$). A graph with a vertex cover of size $k$ has an independent set of size $n-k$, so we no longer have $n$ restricted to the polynomial part.

This separation is one of the basic conjectures of Parameterized Complexity. Parameterized Complexity is a bivariate complexity theory where problems are given with not only the normal input, but also a parameter. For example the (natural) parameterized version of Vertex Cover is:

Vertex Cover
Input: A graph $G$, a positive integer $k$.
Parameter: $k$.
Question: Does $G$ have a vertex cover of size at most $k$?

So each parameterized problem has two (formally explicit) metrics: the size of the input $n$, and the parameter $k$. We then say that a problem $\Pi$ is fixed-parameter tractable if there is an algorithm that decides each instance $(x,k)$ of $\Pi$ in time bounded by $f(k)\cdot|x|^{O(1)}$ for some computable function $f$ dependent only on $k$ (i.e. polynomial with constant degree in $|x| = n$, but essentially free in $k$). We call the class of all such problems $FPT$.

So Vertex Cover is in $FPT$ when parameterized by the size of the vertex cover.

The main intractability framework for Parameterized Complexity is called the $W$-hierarchy, a series of classes $W[t]$ where $W[i] \subseteq W[i+1]$ and $FPT \subseteq W$. Although it's split into lots of classes, the $W$-hierachy bears a practical relationship to $FPT$ in a similar manner to that of $NP$ to $P$, in that if a problem is $W[t]$-hard for some $t$, then it has no $FPT$ algorithm unless $W[t] = FPT$, and we conjecture that $FPT \subset W$ for similar reasons to $P \subset NP$.

Getting back to your question again, finally, it turns out that Independent Set is $W$-complete when parameterized by the size of the independent set. That is, unless $W = FPT$, Independent Set has no algorithm with running time bounded by $f(k)n^{O(1)}$ for any $f$, where $k$ is the size of the independent set.