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$?
$\begingroup$
$\endgroup$
-
1$\begingroup$ What do you about algorithms for vertex cover? $\endgroup$ – Juho Apr 25 '19 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 '19 at 8:11
-
$\begingroup$ I think this problem is duplicate of cs.stackexchange.com/questions/99710/… . $\endgroup$ – Mohsen Ghorbani Apr 25 '19 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 '19 at 8:50
-
$\begingroup$ @LukeMathieson "Bounded Search Tree" does work, thanks $\endgroup$ – galah92 Apr 25 '19 at 15:32
$\begingroup$
$\endgroup$
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.
-
$\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
