Models of Computation - Mathematics 450 - Spring 2005

For HW #24

For a graph G, V(G) and E(G) denote, respectively, the set of all vertices and edges of G. Vertices are often labeled by numbers, and edges are often denoted by their endpoints. For example, if e is an edge whose endpoints are vertices 5 and 8, then e = (5,8) or {5,8}. A subset S of V(G) is said to be independent if no two vertices in S are adjacent.

Problems marked [Optional] should be done, but turn them in only if you're not sure how to do them.

1. [Optional] See page 165 in Wilf for this problem:

1. Give the answer to the Bin Packing problem when S = {1, 2, 3, 4, 5} and K = 7 and N = 3.
2. Give the answer to the Bin Packing problem when S = {1, 2, 3, 4, 5} and K = 8 and N = 2.
3. Give the answer to the Bin Packing problem when S = {1, 2, 3, 4, 5} and K = 7 and N = 2.

1. (The definition of the adjacency matrix can be found in Wilf, page 166.)

   1. Give the adjacency matrix of K₄, the complete graph on four vertices.
   2. Draw a graph whose adjacency matrix has rows: 0,1,0,0; 1,0,1,1; 0,1,0,0; 0,1,0,0.
   3. Is every square matrix of 0's and 1's the adjacency matrix of some graph? Prove your answer.

    

2. [Optional] What does an instance of a problem mean? Give an instance of TSP.
3. On page 168 (Wilf), line -12 ("negative 12" means lines from the bottom), it says:
   "The extra multiplicative factor of log n will not alter ..."
   1. Why is it "multiplicative" and not "additive"?
   2. Where does "log n" come from?
   3. Why does this extra factor not alter the polynomial versus nonpolynomial running time distinction?

    

4. Give the set of all 2x2 and 3x3 adjacency matrices in the "Graph 3-Coloring language" (see bottom of page 168 in Wilf).
5. Wilf, page 170, line 24: "It finally checks that for each edge e of G, it is true that ..."
   It is pretty clear that the two steps before this one take O(n) steps. What is the maximum number of steps does this third step can take? Explain.
6. Wilf, page 170, line -4: "Any suggestions for a certificate?"
   I have a suggestion:
   List all possible tours, and next to each, write its total length. This can be done algorithmically. Creating the list may take very long, but not an issue here (why not?). This is my "certificate".
   Verifying the certificate is easy: just add up the relevant inter-city distances for each tour to check that the total given for each tour in the list is correct, and then check that none of these totals is less than K.
   
   What's wrong with my "proof" that the problem "There is no tour of length less than K" is in NP?