1
$\begingroup$

I know that when we want to find out if Vertex Cover of size $k$ when $k \leq C$, belongs to P or not (when $C$ is some constant), we actually can find algorithm with polynomial time complexity (in the algorithm we iterate over subsets $V'$ such that $|V'|=C$). But what about $k \geq C$?

I personally think it's not in P because $k$ can be as most in size $|V|$, and therefore the time complexity is exponential, but I'm not sure if I'm right (maybe it's unknown?)

$\endgroup$
5
  • $\begingroup$ It's not clear what you are asking. Do you want to find any vertex cover of size greater than $C$? If so, this is trivial, as $V$ is a vertex cover. Or do you want to know if the smallest vertex cover has size greater than $C$? If so, you can do it in polynomial time since, as you say, finding if there is a vertex cover of size at most $C$ can be done in polynomial time. On the other hand, if you want to find the smallest $K$ such that there is a vertex cover of size $K$, then this is of course NP-hard. $\endgroup$
    – Highheath
    Apr 21 at 9:53
  • $\begingroup$ If that makes it more clear,I ask If i can make decider in polynomial time for the Vertex cover problem of size K, and K is greater than C. $\endgroup$
    – micmic
    Apr 21 at 17:37
  • $\begingroup$ Aah, I understand. Yes, this is NP-complete. There is a very simple reduction from "normal" Vertex Cover to your problem here. Can you find it? $\endgroup$
    – Highheath
    Apr 21 at 20:59
  • $\begingroup$ these are my thoughts: I add some vertex to the original graph (100 vertex maybe? according to the problem i showed),and connect it to original vertex in the graph.now we have edges from the new vertex to each one of the original vertex. Then we check with the new decider on my problem,if it returns true,then original graph also should return true. otherwise,false. Im not sure if what I wrote is true.If not,i would glad for for right answer. $\endgroup$
    – micmic
    Apr 25 at 20:35
  • $\begingroup$ Sorry for the late answer. Yes, if you just add some other graph to your original graph that has vertex cover number 100 (for example a path on 200 edges), then your original graph has a VC of size $k$ iff the new graph has a VC of size $k+100$ $\endgroup$
    – Highheath
    May 4 at 8:29
1
$\begingroup$

We don't actually iterate over subsets $V'$ of size $C$, because that would be running in time $\Theta (n^k)$. While that is polynomial for fixed $k$, there is an algorithm that runs in time $O(2^k \cdot n)$, which is much better.

The problem you have stated is not really very well defined, so let's try to clear it up.

The Vertex Cover problem is given a graph $G$ and a number $k$ and asks whether there exists a vertex cover in $G$ of size at most $k$. This problem is NP-complete (as long as $k$ is not a constant).

However, if you ask to find any vertex cover in $G$, then you can reply with $V(G)$, which has size $n$. This version is of course polynomial time solvable and uninteresting.

The answer is therefore: Vertex Cover is NP-complete. If you fix the bounds, however, you can solve the problem in time "polynomial" time (exponential in the bounds).

$\endgroup$
3
  • $\begingroup$ so to understand better,for example: if k>100 , thats mean I can create algorithm that return true of false for this problem in polynomial time because it has fixed bound (100<k<|V|)? $\endgroup$
    – micmic
    Apr 21 at 17:32
  • $\begingroup$ I wanted to add to my last comment: doesn't it make the time complexity of the algorithm exponential because of the right bound |V| ? $\endgroup$
    – micmic
    Apr 21 at 17:47
  • $\begingroup$ Not the answerer, but I'll go: The statement of your second comment is correct, but not the statement of your first comment, as $|V|$ is not a constant bound. $\endgroup$
    – Highheath
    Apr 22 at 22:43

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.