## Algorithm Design Techniques

**COMP-360
Assignment 4
Due: Tues, April 1 in class **

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.

In NP-completeness proofs, you may assume that SAT, 3-SAT, IND
SET, VERTEX COVER, and SUBSET SUM are known to be NP-complete.

1. CLIQUE: Input: Graph
G=(V,E), integer k.

Question: Is there a subset S of V with |S|=k such that every pair of
vertices in S is joined by an edge in E?

(a) Show this problem is NP.

(b) Give a direct reduction from SAT(Text, P. 460) to CLIQUE, and
prove its correctness.

(c) Illustrate your reduction by constructing the CLIQUE input
corresponding
to the SAT input:

(x_{1} + x_{2}
)(x_{1} + x_{2}
+ x_{3}
+ x_{4})(x_{2} + x_{3})(x_{2}
+ x_{3} +x_{4})

2.
Text, P. 505 problem 3. Hint: The problem is NP-complete even if each
sport is known by exactly two
councillors.

Also show how to formulate the original problem as an integer program.

3. Review text pp. 266-271
which shows how to solve the SUBSET SUM problem by dynamic programming.

In class we reduced 3-SAT to SUBSET SUM. Explain in detail why these
two results do not imply that
P=NP.

4. 3-SCHED: Input: The
processing times t_{1 }, t_{2}, ... , t_{n} of
n jobs, and a deadline T. All data are integers.

Each of the jobs must be scheduled on one of three identical machines.
Each machine can process one job at a time.

Question: Is there a schedule so that all jobs finish before time T?

(a) Show that 3-SCHED is NP-complete.

(b) Show how to formulate the problem of finding the smallest T
for which there exists a 3-SCHED as an integer program.

(c) Use lp_solve to solve part (b) for the 9 jobs with processing times
104, 121, 145, 147, 150, 166, 168, 191, 194.