1

In my research I confront a variant of the vertex cover problem as follows:

Given a graph G, a vertex v and a number k, to decide whether G has a vertex cover of size k that contain v.

I have search all over literature and could not find a similar problem. I am interested in the complexity of this problem ( I have proved that it complete for $P^NP[long]$ ).

The question is have you ever seen such variant of vertex cover problem? How do you call this problem ?

user12529
  • 19
  • 1

1 Answers1

1

Given a graph G and a integer K, to decide whether G has a vertex cover of size K is the decision problem of minimal vertex cover problem. And it is NP-complete.

If fact, the problem you described is no difference with that one. That is because if you have contained vertex v, you can remove v and all edges having v as an end-point. What you should do next is to decide whether you can cover the left sub-graph with k-1 vertices.

notbad
  • 2,797
  • 3
  • 23
  • 34