NP Complete, Vertex Cover Problem

Optimization and Bound

Most optimization problems may be replaced with a seemingly simpler transformation that asks whether one can do better than a given bound, instead of asking for the best possible solution. The traveling salesman problem, described in the previous section, is a classic example. If a tm finds the optimal path than it can certainly answer the question: is there a path through these cities that costs less than b for some bound b. Converrsely suppose some tm can tell you whether there is some path that costs less than b. Compute the cost of any path through the cities and set b equal to half this cost. Use binary search until you zero in on the optimal path.

There are a few restrictions that are satisfied by almost every optimization problem. There must be an e that represents the smallest difference between two paths. Thus when you have narrowed the range of minimal costs to within e, you have in fact found the minimal cost and the optimal path. The weights on the edges are usually integers, so set e = 1.

The minimal spanning tree provides a path whose total cost is less than twice the sum of the edge costs, a number whose length is bounded by the size of the problem instance. Each iteration cuts this value in half, as we approach the optimal solution. We need at most n iterations, for n bits, hence the problem remains polynomial in time.

If the weights on the edges are rational numbers, scale up to integers and apply the above reasoning. If all the denominators are relatively prime, multiplying through by a common denominator could square the size of the problem, but we're still under the polynomial umbrella.

All this needs to be made more rigorous, but that depends on the details of the problem. I'm just presenting an outline, which usually proves that finding the best solution is equivalent to finding a solution that is better than b, for an arbitrary bound b. A polynomial time algorithm for either implies a polynomial time algorithm for the other. Let's apply this principle to the vertex cover problem.

Vertex Cover Problem

Given a graph, find a smallest set of vertices that is incident to every edge in the graph. As described above, we transform this into a bounded version of the same problem: is there a set of k vertices such that every edge is incident to some vertex in this set? Since k is bounded by the number of vertices, binary search will find the best k very quickly.

Given an instance of 3-sat, assign a vertex to each atom and connect all three vertices in each clause. Also, connect every x to every ~x, every y to every ~y, and so on. The boolean expression is satisfied iff a cover ≤ 2n can be found, where n is the number of clauses.

In this case any cover ≤ 2n is exactly 2n, or one of the triangles associated with a clause would have two vertices (and an edge) not in the cover.

Given a boolean solution, pick any true atom in each triangle and throw the other two vertices in the cover. That takes care of the edges in all the triangles. If an edge connects x to ~x, they can't both be true, so at least one is in the cover, and is incident to that edge.

Conversely, assume a cover ≤ 2n, in other words, a cover equal to 2n, has been found. The cover includes exactly two points from each triangle. Declare the third atom as true. If x is declared true in this manner, is ~x ever declared true? No - because ~x would not be in the cover, and the edge from x to ~x would remain. Therefore the variables are assigned consistently, and in a manner that satisfies all the clauses. If a variable is unassigned, set it to true or false as you like. Therefore a vertex cover of 2n is equivalent to 3-sat, and the vertex cover problem is np complete.