Vertex Cover of size at most $\log n$

Question

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

@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$. — galah92, Apr 25 '19 at 8:11
I think this problem is duplicate of cs.stackexchange.com/questions/99710/… . — Mohsen Ghorbani, Apr 25 '19 at 8:44
en.wikipedia.org/wiki/Vertex_cover#Fixed-parameter_tractability has enough information to figure this out simply. — Luke Mathieson, Apr 25 '19 at 8:50

Pål GD · Accepted Answer · 2019-04-25 20:44:24Z

4

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.

answered Apr 25 '19 at 16:46

Pål GD

7,51024 silver badges43 bronze badges

$\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 '19 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 '19 at 5:23

add a comment |

1 Answer 1