2
$\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$?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ What do you about algorithms for vertex cover? $\endgroup$ – Juho Apr 25 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 Apr 25 at 8:11
  • $\begingroup$ I think this problem is duplicate of cs.stackexchange.com/questions/99710/… . $\endgroup$ – Mohsen Ghorbani Apr 25 at 8:44
  • 3
    $\begingroup$ en.wikipedia.org/wiki/Vertex_cover#Fixed-parameter_tractability has enough information to figure this out simply. $\endgroup$ – Luke Mathieson Apr 25 at 8:50
  • $\begingroup$ @LukeMathieson "Bounded Search Tree" does work, thanks $\endgroup$ – galah92 Apr 25 at 15:32
4
$\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.

|cite|improve this answer
$\endgroup$
  • $\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$ – Oren Milman Jun 8 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$ – Oren Milman Jun 9 at 5:23

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.