# Vertex Cover - upper bound

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

-
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
add comment

## 1 Answer

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

-
add comment