# Homework 4

Due on Monday, October 11, 1999 at the beginning of class (9:00 p.m.)

#### Problems:

1. Multiprocessor Scheduling
• Given:
• A finite set A of "tasks",
• a "length" l(a) for each a in A, where l(a) is a positive integer,
• a number m of "processors", where m is a positive integer,
• a "deadline" d, where d is a positive integer.
• Answer: "Yes", if there is a partition A = A_1 union A_2 ... union A_m of A into m disjoint sets such that: max_{1<=i<=m} [ sum_{a in A_i} l(a) ] <= d. In other words, all tasks assigned to each of the processors can be processed before the deadline.
Show that the Multiprocessor Scheduling problem is NP-complete.

Hint: Reduce Subset-Sum to Multiprocessor Scheduling.

``` Try making the reduction into 2 steps:

(1) Show that the PARTITION problem is NP-Complete

where:

The partition problem is defined as follows:

GIVEN: A multiset (i.e. a set in which repetition
of elements is allowed) of positive integers
{x_1,...,x_k}

ANSWER: "YES" if there is a subset {y_1,...,y_l}
of {x_1,...,x_k} such that
y_1 + ... + y_l = 1/2 * (x_1 + .... + x_k).
In other words, the multiset can be split into
two parts, each one summing up to half the sum
of all elements in the multiset.

(1.1) Show that PARTITION belongs to NP.
(1.2) Show that SUBSET-SUM <=p PARTITION
Hint: Construct the polynomial time
transformation between the two problems
"inspired" in the following example:

({1,6,11}, 7) belongs to SUBSET-SUM
if and only if
({2,12,22},14) belongs to SUBSET-SUB
if and only if
{2,12,22,8} belongs to PARTITION, i.e.
it can be split into two parts
having the same sum (namely, {2,12,8}
and {22}). Note that
8 = |(2+12+22) - (2*14)|

(2) PARTITION <=p MULTI-PROCESSOR
(this part is fairly easy.)

```

2. 3Color
Consider the 3Color problem described in problem 7.34. Show that the 3Color problem is NP-complete. (You don't need to show that the problem is in NP, since we already proved it in homework 3).

Hint: Reduce 3SAT to 3Color, i.e. show that 3SAT <=p 3Color:

```
Given an input to 3SAT, i.e. a formula in conjunctive
normal form (or a "3 layer logic circuit") C, construct
a graph G such that:

there is an assignment of values to the variables in C
that makes the circuit to output 1
IF AND ONLY IF
there is a 3coloring of the graph G.

In order to achieve this, follow the steps below:

(1) Provide a word description of how to construct G
given C using the following example as "inspiration":
(see Hint in problem 7.34 of the textbook)

C:  ( x or ~y or z) and (z or t or ~z)

G:
---------------------
|                     |
----- v11   ------ v14          v21   ------ v24       |
|     /   \  |     /   \        /   \  |     /   \      |
|    /     \ |    /     \      /     \ |    /     \     |
|   v12----v13   v15----v16   v22----v23   v25----v26   |
|    |            |       \    |            |      |    |
|    |            |        \   |            |      |    |
|    |             ------   \  |       -------------    |
|    |                   |   \ |      |     |           |
|    x --- ~x     y --- ~y     z --- ~z     t --- ~t    |
|    |      |     |      |     |      |     |      |    |
|    |      |     |      |     |      |     |      |    |
|     ---------------------------------------------     |
|                           |                           |
|                           R                           |
|                         /   \                         |
|                        0 --- 1                        |
|                       / \                             |
-----------------------   -----------------------------

Think of 0, 1, R as the 3 colors available to color the graph.

(2) Show that G can be constructed in polynomial time in the
size of C.

(3) Show that there is a way to 3color the resulting graph G
IF AND ONLY IF at least one of the literals in each clause
is assigned color/value 1.
```

3. Traveling Salesperson
• Given:
• A set of n cities {c1,...,cn},
• an integer k, and
• a set of n(n-1)/2 distances {d_1,2, d_1,3, ..., d_1,n, d_2,3, ..., d_2,n, d_n-1,n} between the n cities.
• Answer: "Yes", if there is a cicle {ci1, ..., cin} of the cities such that the length l = d_i1,i2 + d_i2,i3 + .... + d_i(n-1),in + d_in,i1 of the cicle satisfies l <= k.
Show that the Traveling Salesperson problem is NP-complete. (You don't need to show that the problem is in NP, since we already proved it in homework 3).

Hint: Reduce Hamiltonian Path to Traveling Salesperson.