4
$\begingroup$

Consider the following language: $$ L = \{ G | G \text{ has a VC of size at most } \log n \} $$

Does $L\in P$ or $L\in NPC$?

$\endgroup$
5
  • 1
    $\begingroup$ What do you about algorithms for vertex cover? $\endgroup$
    – Juho
    Commented Apr 25, 2019 at 8:07
  • $\begingroup$ @Juho I know $VC \in NPC$ obviously (verified easily). I also know that the language of graphs that has $VC$ of size at most $|V|/2$ is also in $NPC$ (proved using reduction from original $VC$ problem). But the same trick doesn't scale for $\log n$. $\endgroup$
    – galah92
    Commented Apr 25, 2019 at 8:11
  • $\begingroup$ I think this problem is duplicate of cs.stackexchange.com/questions/99710/… . $\endgroup$ Commented Apr 25, 2019 at 8:44
  • 3
    $\begingroup$ en.wikipedia.org/wiki/Vertex_cover#Fixed-parameter_tractability has enough information to figure this out simply. $\endgroup$ Commented Apr 25, 2019 at 8:50
  • $\begingroup$ @LukeMathieson "Bounded Search Tree" does work, thanks $\endgroup$
    – galah92
    Commented Apr 25, 2019 at 15:32

1 Answer 1

5
$\begingroup$

If you solve Vertex Cover with the simple branching algorithm, you achieve an FPT running time of $2^k \text{poly}(n)$, where $k$ is an upper bound for the solution you are looking for.

Substituting $k$ for $\log n$ gives you the answer you are looking for.

$\endgroup$
2
  • $\begingroup$ Doesn't your answer assume that one cannot encode in $\text{poly}(k)$ a graph with $n=2^k$ vertices, while only the first $k$ vertices are not isolated? (See my answer) $\endgroup$ Commented Jun 8, 2019 at 10:16
  • $\begingroup$ Thank you for helping me to realize the convention is to assume that the length of the encoding of a graph is in $\Omega(|V|)$. I deleted my answer. (If you think I should undelete it, please say so.) $\endgroup$ Commented Jun 9, 2019 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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