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

Question

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.

Answer 1

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.