Hardness of FPT problems

Vertex Cover can be easily reduced to Independent Set and vice versa.

However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A kernel with $2k$ vertices exists for Vertex Cover, but Independent Set is W1 hard.

How does the nature of Independent Set change in the context of FPT and why?

Main idea of the answer: if we reduce an instance of parameterized Independent Set to parameterized Vertex Cover, then the parameter than we end up with depends on the size of the graph, and does not only depend on the input parameter. Now for some more detail.

As you know, a parameterized problem $Q$ is in (uniform) FPT if there is an algorithm that decides whether an input $(x,k)$ is contained in $Q$ in time $f(k) |x|^{O(1)}$ for some function $f$.

Since you can decide whether a graph $G$ has a vertex cover of size $k$ by picking an edge, and branching on which of its two endpoints to put in the vertex cover, this branching only goes $k$ deep (else you've put more than $k$ vertices in the cover), and easily runs in time $O(2^k n^2)$; therefore $k$-Vertex Cover is in FPT.

Now suppose we want to try use this algorithm to show that parameterized Independent Set is in FPT; assume we are given a graph $G$ on $n$ vertices and want to decide whether it has an independent set of size $\ell$. This is equivalent to asking whether $G$ has a vertex cover of size $n - \ell$. So we use our above algorithm to compute the answer in $O(2^{n - \ell} n^2)$ time. For our FPT algorithm, the exponential function in the running time may depend on the parameter, which is $\ell$, but it may NOT depend on the size of the input, which is $n$; but the approach we sketched uses time exponential in $n - \ell$ and is therefore not an FPT parameter with respect to the parameter $\ell$. This is why the fact that Vertex Cover is in FPT does not imply that Independent Set is in FPT.

• Thanks for all the replies. In context of parameterized complexity, I understand the idea when I try to study the hardness of Independent set, reasoning out from Vertex Cover. However, I didn't find any explanation that looks at Independent Set , independent of the context of Vertex cover? Is there something in the structure(or the inherent nature) of finding an Independent Set that makes it more harder? – Nikhil Feb 14 '11 at 20:20
• Bart, why is there no parameter $k$ for which the reduction works as desired? – Raphael Feb 15 '11 at 9:30
• @Raphael : Could you clarify your question? The only parameters "allowed" by the OP's question are the respective solution sizes. If we allow arbitrary parameters, then there are many for which the reduction works as desired (If I understood this phrase correctly): For example, if we keep the parameter as "size of the minimum-size vertex cover" for both problems, then both are FPT; MinVC by Bart's argument, and MaxIndSet by the same argument and using the OP's reduction. It is only when we insist that MaxIndSet's paramter be its solution size that the problem becomes W[1]-hard. – gphilip Feb 18 '11 at 14:05
• You understoof my question perfectly! In that sense, the OP's question is ill-posed: it makes only sense to talk about parametrised complexity for pairs of (unparametrised) problem and parameter. I mentally filled the gap with a "forall", meaning that I read Bart's answer in the "for all $k$" sense, too, and thought it was wrong/incomplete. Therefore my question. Other answers have the same problem, by the way. Apparently everybody but me fills the gap with the canonical choice. – Raphael Feb 18 '11 at 15:08

I wouldn't say that the 'nature' of the problem changes, whatever that is supposed to mean. All that changes is the parameter, that is, the way in which you measure the difficulty of the problem.

Graphs that have a vertex cover of size at most $k$ are so structured that it's possible to efficiently reduce them in size: We can greedily find a maximal matching of size at most $k$ and the rest of the graph is an independent set of size at least $n-2k$. Using reduction rules such as the crown reduction, the number of vertices can be reduced to at most $2k$.

On the other hand, graphs which have vertex covers of size at most $n-k$ (or equivalently, maximum independents have size at least $k$) don't seem to have such a simple structure. This can be made precise, as you point out: their structure allows us to encode any $W[1]$-problem.

The following may give some intuition for the difference. A subset of vertices S is a vertex cover of G=(V,E) if and only if V-S is an independent set, so if MVC is the size of a minimum vertex cover then MIS=|V|-MVC is the size of the maximum independent set. An FPT algorithm parameterized by X allows exponential runtime as a function of X. A random graph on n vertices with edge probability one half has with high probability MIS of size about 2logn and MVC of size about n-2logn. Thus, at least for these graphs, an FPT algorithm parameterized by MVC simply allows much more time than one parameterized by MIS.

Though I agree with what others have said, another way I find helpful when thinking about these things is to recast the problem as a recognition problem, i.e. "Does the input graph belong in the family of graphs that have vertex cover at most k?"/"Does the input graph belong in the family of graphs that have independent set at least k?".

Intuitively, a more restricted family of graphs should be easier to recognize than a richer, more general one. The family of graphs of vertex cover at most k is very restricted, in fact each such graph can be described using just $O(k^2+2^k\log n)$ bits, which is much less than the usual $O(n^2)$ bits needed, assuming that k is significantly smaller than n. The family of graphs of independent set at least k on the other hand is very rich: any graph can be edited to belong to it by removing at most $k^2$ edges.

So for me this is one intuitive explanation why I would expect it to be easier to recognize small vertex cover than small independent set. Of course it should be obvious that the above thoughts are nowhere near a formal argument and I guess that at the end of the day the most convincing evidence that it is indeed harder to recognize independent set of size k is exactly the W-hardness of independent set!

• How is the removal of $k^2$ edges enough to give a graph an independent set of $k$ vertices? I would think you'd need $\binom{k}{2} + k \cdot (n - k - 1)$ edge removals if you want to get an independent set of size $k$ in a complete graph on $n$ vertices. – Bart Jansen Feb 15 '11 at 9:37
• @Bart: For an independent set of $k$ vertices, you only need to ensure that no edge exists between these $k$ vertices, and there is at most $k \cdot (k-1) \leq k^2$ edges in a (simple) subgraph of order $k$. – Mathieu Chapelle Feb 16 '11 at 9:34

This is a very indirect answer, and might not quite address your concern. But FPT and the W hierarchy are closely linked with approximability (FPT problems often have PTASs etc). In that context, note that for any graph, VC = n - MIS, and so an approximation for VC doesn't give an approximation for MIS. This is why you need L-reductions for approximations. I suspect there's an equivalent "kernel-preserving reduction" notion for parameterized complexity as well.

• Is there a "kernel-preserving reduction" notion in FPT? – Nikhil Feb 14 '11 at 6:52
• I don't know: hence the quotes :). I'm waiting for the parametrized complexity experts to chime in. – Suresh Venkat Feb 14 '11 at 7:13
• You just summoned it! ;) – Raphael Feb 14 '11 at 7:21
• There is such a notion: a polynomial time-and-parameter transformation. Parameterized problem P polynomial-time-and-parameter transforms to Q (read: $P \leq _{ptp} Q$) if there is a polynomial time algorithm which given an instance $(x,k)$ of problem $P$, outputs in polynomial time an equivalent instance $(x', k')$ of $Q$ such that $k' \in k^{O(1)}$. The use for kernelization is as follows: if $P \leq_{ptp} Q$, $Q$ has a polynomial kernel and the classical versions of $P$ and $Q$ are NP-complete, then $P$ has a poly kernel as well. ( dx.doi.org/10.1007/978-3-642-04128-0_57 ) – Bart Jansen Feb 14 '11 at 11:55
• Another paper stating some relations between approximability and FPT is [dx.doi.org/10.1016/S0020-0190(97)00164-6] where they show that if a problem is W[1]-hard than it cannot admit an efficient PTAS where the objective function is also the parameter. An efficient PTAS has time complexity $O(2^{1/\epsilon}n^k)$, while a time complexity $O(n^{1/\epsilon})$ is not allowed. The same result is also in Bazgan's thesis. – Gianluca Della Vedova Feb 14 '11 at 14:20