## Algorithm Design Techniques

**COMP-360
Assignment 5
Due: Monday, Nov 30, 5pm **

No late assignments!

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.

Except for Problem 1, you may assume that SAT, 3-SAT, IND
SET, VERTEX COVER, SET COVER and SUBSET SUM are known to be NP-complete.

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

Question: Is there a subset S of V with |S|=k such that every edge in E
has at least one endpoint in S?

(a) Show this problem is NP.

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

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

(x_{1} ∨ x_{2}
) ^ (x_{1} ∨ x_{2}
∨ x_{3} ∨ x_{4})
^ (x_{1 } ∨_{
}x_{2}
∨ x_{3})
^(x_{2} ∨ x_{3}
v x_{4})

2.
Text, P. 505 problem 2.

3. Text, P. 513, problem 15

4. You are planning to move
to Asia and are considering whether to ship some of your stuff. Assume
you have n possible items to send.

For each item i, you have a value p_{i}, a weight w_{i}
and a volume v_{i }(you may assume these are all
integers).

For a fixed shipping cost of $C, there is a maximum weight limit of W
and a maximum volume limit of V.

Show that it is NP-complete to decide whether to ship anything or
not, by reducing one of the given NP-complete problems to it.

Formulate the problem as an integer program.

5.
(Worth the same as problems 1-4 combined).

Below are three variations of the 3SAT problem, each of which is
NP-complete.

In each case you have n input variables x_{1 ... }x_{n }
and m clauses with three terms based on three distinct variables in
each clause.

(A term is either x_{i}
or it's complement x_{i}
)

3SAT: Can you
assign truth values to the variables so that each clause has at least one true term?

NAE-3SAT: Can you assign truth values to the variables so that each
clause has either one or two
true terms?

1-OF-3SAT: Can you assign truth values to the variables so that each
clause has exactly one
true term?

Do the following for each problem:

(a) Formulate it as an integer program.

(b) Write a program or script to generate 20 random instances in the
format for lp_solve.

Each of the clauses should contain three terms based on three distinct
variables chosen at
random from the 2n terms.

(c) Set n=40 and using lp_solve determine roughly how
large m should be so that about half of the randomly generated
instances have a "yes" answer.

(d) Now scale up n and m linearly to determine roughly how large an
instance of each type can be solved by lp_solve in 1 minute and in 5 minutes of
cpu time.

Hand in you program/script for part (b). Give statistics on the
outcomes of your experiments to justify your answers to (c) and (d).