1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! I see your point. if problem is not FPT, then 3rd condition of parameterized reduction would be fail. Now, for VC <=_{fpt} IS, we need to create instance of IS from VC, so also k of VC would be in IS as n-k, so second condition is not satisfied here! $\endgroup$ – user777 Jan 21 '18 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.