The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998


Detailed Solutions

Chapter 8, Problem 32




We need to exhibit PTAS reductions to and from Max3SAT: one will establish membership of MaxCut in OptNP and the other will establish completeness. Recall that a PTAS reduction needs three distinct functions: a conventional mapping of instances f, a reverse mapping of solutions g, and a mapping of approximation ratios h.

To develop a PTAS reduction from MaxCut to Max3SAT, we set up a correspondence in which vertices become variables and encode every edge of the graph with a collection of clauses, in usch a way that every cut edge gives rise to a fixed proportion of satisfied clauses in that collection and every uncut edge gives rise to a lower number of satisfied clauses; in order to be able to define g, we also need to ensure that various truth assignments to the variables leave essentially no choice in the structure of the satisfied clauses. Given vertices u and v and edge {u,v}, we will have variables u and v and clauses {u,v} and {u,v}. Since these are not in 3SAT form, we can use our standard expansion with one additional variable (a single one for the entire transformation), call it alpha, and thus obtain four clauses per edge, namely {u,v,alpha}, {u,v,alpha}, {u,v,alpha}, and {u,v,alpha}. Now observe that, if the edge {u,v} is cut in a MaxCut solution, the corresponding truth assignment gives opposite truth values to u and v and thus satisfies all four clauses, whereas, if the edge is not cut, the corresponding truth assignment gives identical truth values to u and v and thus satisfies three of the four clauses. Conversely, in order to satisfy all four clauses, it must be the case that u and v are assigned opposite truth values; any other assignment satisfies three of the four clauses.

Thus we have a reduction from MaxCut to Max3SAT that starting from an instance G=(V,E), produces an instance with |V|+1 variables and 4|E| clauses and is such that a solution that cuts k edges gives rise to a truth assignment that satisfies 3|E|+k clauses and vice versa (any truth assignment handles clauses in blocks of 4 and satisfies either all 4 or just 3 in each block). In particular, if the optimal solution to an instance I of MaxCut has k* edges cut, then the optimal solution to the instance f(I) of Max3SAT has 3|E|+k* satisfied clauses and vice versa; also, if we obtain an approximation for f(I) that is within a ratio epsilon<0 of optimal (i.e., it satisfies epsilon(3|E|+k*) clauses), then the corresponding partition for I cuts floor(epsilon k*) edges, meaning that the precision requirements are identical. Thus we have our f, g, and h, as desired, and we have proved that MaxCut is in OptNP.

To show completeness, we now need a PTAS reduction from Max3SAT to MaxCut. We already have, by transitivity, a polynomial-time transformation from the first to the second (viewed as decision problems) through the intermediate problem of NAE3SAT. Does this compound reduction have the desired properties of a PTAS reduction? The transformation from 3SAT to NAE3SAT uses, for an instance of n variables and m clauses, 2n+24m variables and produces 32m clauses. For each original clause, 32 clauses are produced and all of them are satisfied exactly when the original is; when the original clause is not satisfied, 2 of the 8 intermediate clauses produced are not satisfied and thus 2 of the 24 final clauses are not satisfied. So far, so good: since the numbers are fixed, no problem can arise. Finally, our reduction from NAE3SAT to MaxCut has similar properties: for an instance with n' variables and m' clauses, it produces a graph with 2n'+3m' vertices and n'+6m' edges. Each satisfied clause corresponds to a cut of 5 edges and all n' variable edges are always cut; when a clause is not satisfied, only 3 edges are cut. Again, all values are fixed, so that the compound transformation is a PTAS reduction, with the identity for h and the obvious g.