Cheap and Secure Web Hosting Provider : See Now

[Solved]: Vertex Cover problem modification

, , No Comments
Problem Detail: 

Modification of vertex cover problem.
Given a graph G,does G have a vertex cover with 10 vertices? Is this problem still in NP?
Given a graph G and integer k, does G have a vertex cover with k vertices?
Is there any important difference between this two problems?

Asked By : Dominik_svk

Answered By : Pål GD

For fixed $c$ (i.e., we consider $c$ as a constant) this is trivially solvable in time $n^cm$ which is polynomial in $n$, however, if $k$ is part of the input, then $n^k$ would be considered exponential in $k$.

Vertex cover is solvable in $2^k \cdot n^{O(1)}$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback