Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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}$. – martini Jul 4 '12 at 19:26
@martini You're right, I edited the question, though I think the reduction is still valid. – 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 :-)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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