Introduction to Algorithms December 6, 2003Massachusetts Institute of Technology 6.046J/18.410JProfessors Shafi Goldwasser and Silvio Micali Handout 30Problem Set 9This problem set is not to be handed in.Reading: Chapters34,35.Problem 9-1. The challenges of industrial researchWe say that a graph has a spanning graph of degreeif there exists a subset of edgessuch that (1)is a connected graph and (2) the degree of each vertex inis at most. Such ais called a degreespanning graph of. This problem haspractical applications for telecommunications networks where nodes have bounded degrees.You are working as an algorithms designer for a major telecommunications company. A co-workerof yours has been working on developing an efficient algorithm for the following search problem,SEARCH-SG: given a graph and an integer, find a subset of edgessuch that ! is a degreespanning graph of, if one exists.One day this co-worker leaves the company for a start-up, and the management asks you to takeover his project where he has left off. It turns out that all he has been able to do so far is to design amagic box DECISION-SG#"$%'&(that solves the following decision problem: on input a graph)*and an integer, the magic box outputs+ifhas a degreespanning graph, and,otherwise.(a) Assuming that the magic box that your co-worker designed runs in polynomial time,design a polynomial-time algorithm that solves SEARCH-SG. Prove that your algo-rithm is correct and runs in polynomial time.(b) Suppose that the magic box that your co-worker designed has a bug and does notdo anything meaningful at all. But another co-worker has designed a magic box forthe 3-SAT decision problem. Assuming that her magic box runs in polynomial time,prove that there exists a polynomial-time algorithm that solves the smallest degreespanning graph problem.Problem 9-2. Approximating knapsackRecall from practice quiz 2 the problem of picking out, from a large pile of treasure, the best thingsyou can fit in your knapsack. Specifically, the treasure consists of-objects.0/1.3246575857.:9. Object.<;has size=4;and is worth>?;, for each@A+B1CD4575858-. Your backpack has sizeE, that is, can holda number of objects whose total size is at mostE. You want to carry home as much total worth aspossible.You might remember that on practice quiz 2 we asked you to give an efficient algorithm for thisproblem, assuming that the=<;,>F;andEwere integers. It turns out that that method only works wellwhen the values are small integers— recall that the running time of your algorithm was polynomialinE, not in the size of the encoding ofE, which isGIHE, —in general the problem is NP-hard!2Handout 30: Problem Set 9(a) Show that the knapsack problem is NP-hard by a reduction from the SUBSET-SUMproblem in the book.Probably you’re not going to leave all the treasure sitting there just because you can’t easily figureout how to get the absolute best total worth. So let’s look for an approximation algorithm, that is,one guaranteed to get most of the total worth you can hope for.(b) One obvious algorithm to try is a greedy algorithm: sort the objects in decreasingorder of>F;KJB=6;and go through the list taking an object if it still fits. Show that thereare inputs on which this algorithm might give you an arbitrarily small fraction of theoptimal total worth.(c) Let’s try a slight improvement to part (a): run the greedy algorithm, and find out whattotal worth it would give you. Compare this value to the single most valuable objectthat fits in your knapsack. If the single object is better, take only the single object.Otherwise take the greedy solution. Show that this is a 2-approximation algorithm.(Hint: Reason about the fractional solution—i.e. a solution you would get if you wereallowed to split an object—at the time the greedy algorithm first rejects an object.)Problem 9-3. ReductionsSuppose thatLF/andL2are languages such thatL?/M"NL2. For each of the following statements,either prove that it is true, or prove that it is false, or give a convincing justification for why it is anopen question.(a) LetLF/OL2QPSRUT. IfLV/FPST, thenL2WPST.(b) IfL2WPST, thenLV/FPST.(c) LetL2QPSRUT. IfL2is not NP-complete, then neither isL?/.(d) LetLF/OL2QPSRUT. IfL2("NMLV/, then bothLF/andL2are NP-complete.(e) IfLV/andL2are both NP-complete, thenL2W"NWLV/.Problem 9-4. Easy vs. hard cases of the same problemThe directed Hamiltonian path problem is as follows: given a directed graphXYandtwo distinct verticesZ[\]P^, determine whethercontains a path that starts atZ, ends at\, andvisits every vertex of the graph exactly once.(a) Prove that the directed Hamiltonian path problem is NP-complete. (Hint: consider theHamiltonian cycle problem described in the book.)(b) Design a polynomial-time algorithm that solves the directed Hamiltonian path prob-lem for directed acyclic
View Full Document