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}}$.

  • $\begingroup$ A reduction $f$ must map all pairs $(G,k)$ to graphs $f\bigl((G,k)\bigr)$ such that $(G,k) \in \mathsf{VC} \iff f\bigl((G,k)\bigr) \in \mathsf{VC_{LOG}}$. You can't just map those in $\mathsf{VC}$. $\endgroup$ – martini Jul 4 '12 at 19:26
  • $\begingroup$ @martini You're right, I edited the question, though I think the reduction is still valid. $\endgroup$ – Shmoopy Jul 4 '12 at 19:44

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 :-)


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.