Verification algorithm for minimum vertex cover?

Question

We know that the minimum vertex cover is NP complete, which means that it is in the set of problems that can be verified in polynomial time.

As I understand it, the verification process would require the following:

1. Verify that the solution is a vertex cover at all
2. Verify that the solution is the smallest possible subset of the source graph that satisfies condition #1

I'm finding it hard to establish that step #2 can be done in polynomial time. Can anyone explain how it is?

Answer 1

The minimum vertex cover is NP-hard. It is only NP-complete if it is restated as a decision problem which can be verified in polynomial time.

The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph.

• INSTANCE: Graph G
• OUTPUT: Smallest number k such that G has a vertex cover of size k.

If the problem is stated as a decision problem, it is called the vertex cover problem:

• INSTANCE: Graph G and positive integer k.
• QUESTION: Does G have a vertex cover of size at most k?

Restating a problem as a decision problem is a common way to make problems NP-complete. Basically you turn an open-ended problem of the form "find the smallest solution k" into a yes/no question, "for a given k, does a solution exist?"

For example, for the travelling salesman problem, verifying that a proposed solution the shortest path between all cities is NP-hard. But if the problem is restated as only having to find a solution shorter than k total distance for some k, then verifying a solution is easy. You just find the length of the proposed solution and check that it's less than k.

The decision problem formulation can be easily used to solve the general formulation. To find the shortest path all you have to do is ratchet down the value of k until there are no solutions found.