<p>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.</p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-14T20:20:22.703Z
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
CC BY-SA 2.5
2011-02-15T09:30:04.613Z
Bart, why is there *no* parameter $k$ for which the reduction works as desired?
Raphael
CC BY-SA 2.5
2011-02-18T14:05:58.153Z
@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
CC BY-SA 2.5
2011-02-18T15:08:13.930Z
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
CC BY-SA 2.5
2011-02-14T12:36:35.850Z
2011-02-14T12:36:35.850Z
Bart Jansen
<p>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.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-14T12:37:38.303Z
2011-03-10T12:33:33.167Z
2011-03-10T12:33:33.167Z
Holger
<p>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?".</p>

<p>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.</p>

<p>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!</p>

CC BY-SA 2.5
2011-02-15T09:37:58.783Z
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
CC BY-SA 2.5
2011-02-16T09:34:56.900Z
@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
CC BY-SA 2.5
2011-02-15T00:41:05.170Z
2011-02-15T00:41:05.170Z
Michael Lampis
<p>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. </p>

CC BY-SA 2.5
2011-02-14T06:52:24.207Z
Is there a "kernel-preserving reduction" notion in FPT?
Nikhil
CC BY-SA 2.5
2011-02-14T07:13:36.980Z
I don't know: hence the quotes :). I'm waiting for the parametrized complexity experts to chime in.
Suresh Venkat
CC BY-SA 2.5
2011-02-14T07:21:54.800Z
You just summoned it! ;)
Raphael
CC BY-SA 2.5
2011-02-14T11:55:28.367Z
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. ( http://dx.doi.org/10.1007/978-3-642-04128-0_57 )
Bart Jansen
CC BY-SA 2.5
2011-02-14T14:20:44.413Z
Another paper stating some relations between approximability and FPT is [http://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
CC BY-SA 2.5
2011-02-14T19:36:34.880Z
These are great ! maybe they should be answers themselves !
Suresh Venkat
CC BY-SA 2.5
2011-02-14T06:27:56.757Z
2011-02-14T06:27:56.757Z
Suresh Venkat
<p>Vertex Cover can be easily reduced to Independent Set and vice versa.</p>

<p>However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A <a href="http://en.wikipedia.org/wiki/Kernelization">kernel</a> with $2k$ vertices exists for Vertex Cover, but Independent Set is <a href="http://en.wikipedia.org/wiki/Parameterized_complexity#W.5B1.5D">W<a href="http://en.wikipedia.org/wiki/Kernelization">1</a> hard</a>.</p>

<blockquote>
  <p>How does the nature of Independent Set change in
  the context of FPT and why?</p>
</blockquote>

<cc.complexity-theory><parameterized-complexity><fixed-parameter-tractable>
Hardness of FPT problems
Nikhil
# Hardness of FPT problems

(Asked by: username_0 on 2011-02-14)

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](http://en.wikipedia.org/wiki/Kernelization) with $2k$ vertices exists for Vertex Cover, but Independent Set is [W[1](http://en.wikipedia.org/wiki/Kernelization) hard](http://en.wikipedia.org/wiki/Parameterized_complexity#W.5B1.5D).

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

**Tags:** cc.complexity-theory, parameterized-complexity, fixed-parameter-tractable

---

## 4 answers

### Answer by username_1 on 2011-02-14. Score: 9

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: Bart, why is there *no* parameter $k$ for which the reduction works as desired?  
> **username_3**: @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.  
> **username_2**: 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.  

---

### Answer by username_4 on 2011-02-14. Score: 6

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.


---

### Answer by username_5 on 2011-02-15. Score: 4

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!

> **Comments:**
> **username_1**: 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.  
> **username_6**: @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$.  

---

### Answer by username_7 on 2011-02-14. Score: 3

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.

> **Comments:**
> **username_0**: Is there a "kernel-preserving reduction" notion in FPT?  
> **username_7**: I don't know: hence the quotes :). I'm waiting for the parametrized complexity experts to chime in.  
> **username_2**: You just summoned it! ;)  
> **username_1**: 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. ( http://dx.doi.org/10.1007/978-3-642-04128-0_57 )  
> **username_8**: Another paper stating some relations between approximability and FPT is [http://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.  
> **username_7**: These are great ! maybe they should be answers themselves !  

---

