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₁ , a₂ , ... , a_n , b, and profits c₁, c₂ , ... , 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.