Carnegie Mellon University, Computer Science Department Graduate Algorithms 15-750, Spring 2004, Instructor: Manuel Blum TA: Doru Balcan Homework Assignment #5 Important Note: Each problem is worth 10 points. The solutions are expected by Monday, Mar 22, at the beginning of the class (IN CLASS). Any hand-ins after this deadline shall not be taken into consideration. 1. Given a graph G = (V,E), and a weight function w:V-->N*, find a matching M of G that maximizes the sum of the weights of the endpoints of all edges in M. You can proceed either: a. by a direct argument (with proof), stating also an algorithm to obtain the solution, or b. by identifying a certain matroid structure (V, Mat), (with proof), and applying the Red-Blue rules introduced earlier in the course (such a matroid is called a "matching matroid".) 2. Consider again a graph G=(V,E), this time - together with a weight on the EDGE set. We're now interested in finding a matching M of G, that maximizes the sum of the weights of all edges in M. Is this problem the same as the previous one? If you answer "yes", give a reason why it is so; if you answer "no", give a counterexample. NOTE: There might exist a little ambiguity over what it means that the two problems are "the same". One possible way to interpret, this is to check whether an algorithm used for solving one of them, can be slightly modified to solve the other. For instance, finding the minimum of a function f is "the same" as finding the maximum of the function g=-f. So, in the particular case of our weighted matching problem(s), the question we ask here is whether placing weights on the edges of the graph is any different from placing them on the vertices. Please notice that the supplementary explanation is about twice as long as the problem itself. 3. The Wandering Salesman Problem (WSP) is the TSP, except that the salesman can start wherever he wishes and does not have to return to the starting city after visiting all cities. a. Show how to transform in polynomial time any instance of the WSP to an equivalent instance of the TSP. b. Show how to transform in polynomial time any instance of the TSP to an equivalent instance of the WSP. (By "equivalent", we mean that the optimal solution of one can be easily derived from the optimal solution of the other.) NOTE: The specific version of the TSP is the same as the "optimization-like" variant presented in class. We shall use the assumption of graph completeness + infinite weights on some edges, in order to model arbitrary graphs. 4. Which of the following problems remain essentially unchanged when we turn them from minimization to maximization problems? Why? a. TSP. b. Shortest path from s to t. c. Minimum weight complete matching. d. MST.