15-451 Algorithms: Lecture 4/11/00

Announcements:

- No recitation Thurs due to Carnival

**********

Topics:  

 I. Hardness of Approximation
     a. Recap
     b. INDEPENDENT SET-B to MAX 2SAT

II. Quiz 2

**********

I. Hardness of Approximation

a. Recap

Polynomial-time approximation scheme (PTAS) for a problem Q: 
Given any fixed epsilon > 0, and any problem instance x of Q,
outputs a solution to x in poly-time (in the size of the input x)
whose relative error
      |alg soln for x - opt soln for x|/ (opt soln for x) 
is <= epsilon.

Desirable because can get arbitrarily close to an optimal answer.

There is a class of problems, called MAX SNP-hard problems, such that
if there were a PTAS for one of these problems, there were be a PTAS for
all of them.  This class includes: MAX 3SAT, MAX 3SAT-B, VERTEX COVER-B,
MAX CUT.

In fact, this stronger result is known:

Thrm: If P not equal to NP, then no PTAS for any MAX SNP-hard problem.

**********

b. L-reduction: INDEPENDENT SET-B to MAX 2SAT

INDEPENDENT SET-B: Find the largest independent set in a graph with
                   vertex degree bounded by B, for a constant B

MAX 2SAT: Given a set of clauses with <= 2 literals per clause, find a truth
          assignment that satisfies the MOST clauses

          E.g., (x1 or x2) and (not(x1) or x3) and not(x2) and not(x3)
                Can satisfy at most 3 of the 4 clauses

Given that INDEPENDENT SET-B is MAX SNP-hard, show that MAX 2SAT is
MAX SNP-hard.

Proof:  Let Q = MAX 2SAT, Q' = INDEPENDENT SET-B

(i) Need to: Select a constant c1 > 0 and
    describe a poly-time algorithm that computes a function f mapping 
    every instance x' of Q' to an instance x = f(x') of Q
    such that (optimal size for x) <= c1 * (optimal size for x')

Take c1 = 1 + B(B+1)/2, and the following mapping:

We have a variable for each node.
For every node u, we have the clause (u).
For every edge (u,v), we have the clause (not(u) or not(v)).

E.g.,     a      
         / \     (a) and (b) and (c) and (d) and (not(a) or not(b)) and
        b---c    (not(a) or not(c)) and (not(b) or not(c)) and
         \ /     (not(b) or not(d)) and (not(c) or not(d))
          d
 
Claim: There exists an optimal assignment that satisfies all the clauses 
corresponding to the edges.

Why? Any optimal solution that fails to satisfy a clause (not(u) or not(v))
can be converted to one that does by setting u = FALSE: it satisfies this
clause and only unsatisfies the clause (u).

Claim: The nodes whose variable is TRUE form an independent set.
Why??? [If (u) and (v) set to TRUE and there is an edge (u,v), 
        then clause (not(u) or not(v)) would be FALSE, contradicting above claim.]

Thus, the maximum number of clauses that can be satisfied is equal to the size
of the maximum independent set plus the number of edges.

Claim: For graphs on n nodes with bounded degree B, the size of the
maximum independent set is >= n/(B+1).
Why??? [Following algorithm selects such an MIS: repeatedly select a node
        and discard all its neighbors, until the graph is empty.]
 
Since the graph has bounded degree B, the number of edges is <= B * (the number
of nodes)/2 because each edge is counted twice in the sum of the degrees of the nodes.

Thus (optimal size for MAX 2SAT instance) = (optimal size for IS instance) + #edges
      <= (optimal size for IS instance) + Bn/2
      <= (optimal size for IS instance) + (B(B+1)/2) * (optimal size for IS instance)
      <= c1 * (optimal size for IS instance)

(ii) Need to: Select a constant c2 > 0 and
     describe a poly-time algorithm that computes a function g mapping 
     solutions s of x with size c to a solution s' = g(s) of x' with size c'
     such that |c' - (optimal size for x')| <= c2 * |c - (optimal size for x)|

Take c2 = 1, and the following mapping:

First convert the MAX 2SAT solution to a solution of no smaller size that 
satisfies all the edge clauses by setting the first variable in each unsatisfied 
clause to FALSE.  (Recall the argument above as to why this has no smaller size.)
The independent set is the set of nodes whose variable is TRUE.

Let I = MAX 2SAT instance and I' = INDEPENDENT SET-B instance

For above, have (alg size for I) <= alg size for I' + #edges.

Then    |(alg size for I') - (optimal size for I')| =
         (optimal size for I') - (alg size for I')  =
         (optimal size for I' + #edges) - (alg size for I' + #edges)  <=
         (optimal size for I) - (alg size for I)   =
   c2 * |(alg size for I) - (optimal size for I)|

Therefore, MAX 2SAT is MAX SNP-hard.
QED