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:
(x1 + x2
)(x1 + x2
+ x3
+ x4)(x2 + x3)(x2
+ x3 +x4)
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 t1 , t2, ... , tn 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.