CODEWITHSUNDEEP
graphcomplexity-theoryvertex-cover
user12529
user12529

Reputation: 19

A variant of the minimum vertex cover

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 ?

Upvotes: 1

Views: 517

Answers (1)

notbad
notbad

Reputation: 2887

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.

Upvotes: 1

Related Questions