Test #2, CS 255, April 5, 2006

There are 150 points on the test.
Problems 1-6 are worth 20 points each; Problem 7 is worth 30 points each

Assuming that P is not equal to NP, which of the following must be true?
1. the subset sum problem is in P
2. any problem in NP is polynomially reducible to TSP
3. if a problem in in NP and TSP is polynomially reducible to it, it is NP-complete
4. there is a problem in P that is NP-complete
5. there is a problem that is in NP, that is not in P, and that is not NP-complete
Trace the GREEDY-SET-COVER approximation algorithm of Section 35.3 of the text on the instance where X = {1,2,3,4,5,6,7,8,9,10} and F has the 10 members S_i for 1 <= i <= 10, where S₁ = {1} and S_i = {x ε X | i divides x evenly} for 2 <= i <= 10.
Recall that we discussed in class a job scheduling problem for which we also discussed a greedy First-Fit Decreasing approxmiation algorithm. Consider the instance in which of this problem where there are 3 processors, and 9 jobs with time requirements of 17, 16, 10, 10, 10, 7, 7, 7, and 6.
1. What approximate solution would the greedy approximation algorithm find for this instance? What is its cost?
2. Show that there is an optimal solution with cost 30, in which all processors finish at the same time.
3. Verify that when you divide the approximate cost that you found above by the optimal cost, the result is less than the approximation ratio that was given in class for this algorithm.
Consider the complete tree of 15 vertices given below.
1. Trace the operation of the text's APPROX-VERTEX-COVER algorithm on this undirected graph. Consider the edges in level order.
2. Given the approximation ratio for this algorithm and the result of your trace, how large must an optimal solution to this instance be?
3. Find an optimal solution of this size.
```
                 1
               /    \ 
             2         3
           /   \      /  \
          4    5     6    7
         / \  / \   / \  /  \ 
        8  9 10 11 12 13 14 15
```
For the graph with vertex set {0,1,2,3,4} and adjacency matrix below, the minimum cost spanning tree contains edges {0,2}, {1,2}, {2,3}, and {3,4} and thus has cost 100. Trace the approximation algorithm APPROX-TSP-TOUR of Section 35.2 of the text on this graph. What is the cost of your approximate solution? Note that the given graph is undirected and has the triangle inequality property.
```
      0 50 40 50 45
     50  0 30 32 52
     40 30  0 10 22
     50 32 10  0 20
     45 52 22 20  0 
```
In the correctness proof for the algorithm of the previous problem,
1. how did we show that the claimed approximation ratio was attained, without knowing the cost of an optimal solution?
2. where was the triangle inequality assumption used?
The subgraph isomorphism problem takes as an instance two graphs G and S, and asks whethere there is a subgraph of G that is isomorphic to S. Although the graph isomorphism problem is not known to be NP-complete, the subgraph isomorphism problem is. Show that the subgraph isomorphism problem is NP-complete (hint: transform from the clique problem). Don't forget to show that the problem is in NP (doing this is worth 10 points). You may assume that a graph with n vertices has a representation of size at least n.