# Vertex Cover of size at most $\log n$

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

• What do you about algorithms for vertex cover? – Juho Apr 25 '19 at 8:07
• @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
• @LukeMathieson "Bounded Search Tree" does work, thanks – galah92 Apr 25 '19 at 15:32

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.
• 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) – Oren Milman Jun 8 '19 at 10:16
• 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.) – Oren Milman Jun 9 '19 at 5:23