## Algorithm Design Techniques

**COMP 360B
Assignment 4
Due: April 11, 2003 5pm**
Assignments are to be left in the box near
the labs, McConnell 1st floor.

Late assignments -10% per day, starting April
14, 5pm.

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, Subset Sum, Independent Set.

1. Study the reduction of SAT to CLIQUE.

Consider the CNF: ( __x__ + y + __z__ ) . ( x + z ) . (__ y__ +
z ) . ( __x__ + y + z) . ( x + __y__ ), where
underlineing represents the complement of the variable .

Construct a graph G such that every clique of size 5 in G corresponds to
a consistent truth assignment for the CNF.

Illustrate by showing two different cliques of size 5.

2. Knapsack: Instance: Non-negative weights a_{1} , a_{2}
, ... , a_{n} , b, and profits c_{1}, c_{2}
, ... , c_{n}^{}, k.

Question: Is there a subset of weights with total weight
at most b, such the the corresponding profit is at least k?
Show Knapsack is
NP-complete. (Hint: Reduce Subset Sum to this problem)

3. Both the clique problem and the vertex cover
problem are solvable in polynomial time for bipartite graphs, but are NP-complete
in general. Does this imply that all NP-complete problems for undirected
graphs are solvable in polynomial time for bipartite graphs? Justify your
answer!

4. Give an example of an NP-complete problem Q that
can be reduced to a problem R solvable in polynomial time using a non-polynomial
time reduction. You may invent the problem R, but be sure to specify
it precisely.