1
$\begingroup$

A few definitions:

  • $\mathsf{VC} = \{ (G,k) \mid \text{There exists a vertex cover of size $k$ in $G$}\}$

  • $\mathsf{VC_{LOG}} = \{ G \mid \text{There exists a vertex cover of size $\leq \log |V|$ in $G$} \} $

Does $\mathsf{VC_{LOG}} \in \mathsf P$? Does $\mathsf{VC_{LOG}} \in \mathsf{NP}\setminus \mathsf P$?

Is there something wrong with the following reduction that shows that $\mathsf{VC \leq VC_{LOG}}$?

Let $(G,k) \ $ where $G = (V,E)$. If $k < \log(|V|)$, return $G$. Else, construct a new graph $G_{k}$, where $G_k = (V_k,E)$ with $ V_k = V \cup \{ v_i \mid 1 \leq i \leq 2^k -|V| \} $

The reason is I want to add enough useless vertices such that $k$ would be $\log |V_k|$ which would translate elements in $\mathsf{VC}$ to elements in $\mathsf{VC_{LOG}}$.

  • 0
    @martini You're right, I edited the question, though I think the reduction is still valid.2012-07-04

1 Answers 1

1

Your reduction is not valid, because you miss the if and only if part. You need an algorithm that transforms all pairs $(G,k)$ into graphs $G_k'$ such that $(G,k) \in VC$ if and only if $G_k' \in VC_{LOG}$. The point of a reduction is to be able to solve $VC$ using an oracle/algorithm that can solve $VC_{LOG}$ in polynomial time. However, with your reduction it is not possible, and also you may need to add a huge (exponential) number of vertices.

Moreover, vertex cover is fixed-parameter tractable (for each unprocessed vertex you take it or take all of its neighbours) and this yields polynomial-time algorithm for $VC_{LOG}$ (e.g. check wikipedia or try to google it). Besides, $VC_{LOG} \in (NP\,\backslash\,P)$ would imply $P \neq NP$ which is a very hard problem.

Hope that helps :-)