Algorithm Design Techniques

COMP-360B Assignment 4 Due: April 13, 2004

Assignments are to be left in the box near the labs, McConnell 1st floor.
Late assignments -10% per day, including weekends.
If you work closely with someone else, indicate the person's name(s) on
your homework. The final write-up of each assignment must, however, be
your own work.

For this assignment, you may use the fact that the following problems are known
to be NP-complete: SAT, 3-SAT(also called 3-CNF-SAT), SUBSET SUM.

1. (a) Give a direct reduction of the 3-SAT problem to the VERTEX COVER problem.
   Draw the graph that you obtain from the expression: ( x + y + z ) . ( x + y+ z ) .(x+ y + z ) . ( x + y + z)
   Find a satisfying truth assignment and show on the grapht that it corresponds to a vertex cover of the same size.

(b) Illustrate the reduction from 3-SAT to SUBSET SUM (Cormen pp1014-6) using the expression ( x + y + z ) . ( x + y+ z ) .(x+ y + z ) . ( x + y + z)
by building a table as in Fig 34.19. Also write out all the numbers for the subset problem in decimal.
Show the equivalence between two different satisying truth assignments and valid subset sums, using the decimal representation of the numbers.

2. 3-Partition: Instance: Non-negative integers a₁ , a₂ , ... , a_n
Question: Can the integers be partitioned into three disjoint subsets of equal weight?

Show 3-Partition is NP-complete.

3. (a) Formulate the following problems as integer linear programs: 3-SAT, VERTEX COVER, SUBSET SUM.

(b) Use lp_solve to find an integer programming solution to the example of each of these problems given in question 1.

2004.4.2