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
    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}$.2012-07-04
  • 0
    @martini You're right, I edited the question, though I think the reduction is still valid.2012-07-04

1 Answers 1