# How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?

We have the following Lemma and proof:

Lemma 5.5. If $$A$$ if FPT, then $$A\leq_{\mathrm{fpt}}$$ Independent Set.

Proof. We reduce $$A$$ to Independent Set parametrised by $$k'$$, where $$k'$$ is the size of a sought independent set. Given an instance $$(x,k)$$ of $$A$$,

• solve $$(x,k)$$ in $$f(k)\cdot \mathrm{poly}(|x|)$$ time, (the running time of this reduction is using the running time of problem $$A$$)

• if $$(x,k)$$ is a yes-instance, then output a one-vertex graph and $$k'=1$$.

• if $$(x,k)$$ is a no-instance, then output a one-vertex graph and $$k'=2$$. (Could this need more time to compute?)

It is clear that the input instance is a yes-instance if and only if the output IS instance is, and $$k'\leq k+2$$. $$\quad\square$$

The definition of parameterized reduction is as follows:

Definition 13.1 (Parameterized reduction). Let $$A,B\subseteq \Sigma^*\times\mathbb{N}$$ be two parameterized problems. A parameterized reduction from $$A$$ to $$B$$ is an algorithm that, given an instance $$(x,k)$$ of $$A$$, outputs an instance $$(x',k')$$ of $$B$$ such that

1. $$(x,k)$$ is a yes-instance of $$A$$ if and only if $$(x',k')$$ is a yes-instance of $$B$$,
2. $$k'\leq g(k)$$ for some computable function $$g$$, and
3. the running time is $$f(k)\cdot |x|^{\mathcal{O}(1)}$$ for some computable function $$f$$.

Now it seems from what he did is: if $$(x,k)$$ is yes-instance, then output a one vertex with $$k'=1$$, otherwise if $$(x,k)$$ is no-instance, then output a one vertex with $$k'=2$$. This makes the first condition of Parameterized reduction true. Now,for second condition, we should say $$k' \leq g(k)$$ where $$g(k)=1$$ if we have yes-instance, and $$0$$ otherwise. The running time would be just the running time of the parameterized algorithm. Done.

My question is that when I want to do a reduction, I should take the input of $$A$$ (like vertex cover) and turn it to input of IS instance. For example assume we have clique of $$4$$, with $$k=3$$, the vertex cover algorithm will return a yes-instance, now if we want to turn this instance to IS to make it yes-instance, we need to use $$n-k$$. But he use different way. Also, when we prove IS to VC using parameterized reduction, it gives us wrong reduction (because of $$n-k$$ isn't a computable function of $$k$$). I just want to know here how "VC to IS" using parameterized reduction works.

It seems your confusion comes from the fact that Lemma 5.5 is a bit of a strange statement. In fact, we can replace Lemma 5.5 with the statement that for any problem $B$ such that $B_Y$ is a yes-instance of $B$ and $B_N$ is a no-instance of $B$ we have that $A\leq_{\mathrm{fpt}}B$. The proof of this adapted lemma is precisely the same as Lemma 5.5, only now we use $B_Y$ in the second bullet-point and $B_N$ is the third.
The crucial reason why this works is that we already know that $A$ is fixed parameter tractable. In a sense, this lemma shows that we learn nothing from a fpt-reduction from a problem we already know is fpt.
So, this lemma is in fact useless when trying to create a reduction from a problem we don't know is fpt, such as $k$-Clique.
When you try to apply Lemma 5.5 when $A$ is not fpt (or at least not known to be), you fail to satisfy part 3 of the definition of an fpt-reduction.