Question

Show that vertex cover is in NP.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

If any problem is in NP, then, given a ‘certificate’ (a solution) to the problem and an instance of the problem (a graph G and a positive integer k, in this case), we will be able to verify (check whether the solution given is correct or not) the certificate in polynomial time.

The certificate for the vertex cover problem is a subset V’ of V, which contains the vertices in the vertex cover. We can check whether the set V’ is a vertex cover of size k using the following strategy (for a graph G(V, E)):

let count be an integer
set count to 0
for each vertex v in V’
    remove all edges adjacent to v from set E
    increment count by 1
    if count = k and E is empty
    then
        the given solution is correct
    else
        the given solution is wrong

It is plain to see that this can be done in polynomial time. Thus the vertex cover problem is in the class NP.

Kindly revert for any queries

Thanks.