CS4123 Theory of Computation. A99
Homework 4

Prof. Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute

Homework 4

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.

Additional Problems for students taking this course for graduate credit:

1. Problem 7.17 from the textbook.