Algorithm Design and Analysis November 12, 2008Pennsylvania State University CSE 565, Fall 2008Adam Smith Handout 13Homework 10 – Due Friday, November 14, 2008Please refer to the general information handout for the full homework policy and options.Reminders• Your solutions are due before the lecture. Late homework will not be accepted.• Collaboration is permitted, but you must write the solutions by yourself without assistance,and be ready to explain them orally to a member of the course staff if asked. You must alsoidentify your collaborators. Getting solutions from outside sources such as the Web or studentsnot enrolled in the class is strictly forbidden.• To facilitate grading, please write down your solution to each problem on a s eparate sheet ofpaper. Make sure to include all identifying information and your collaborators on each s heet.Your solutions to different problems will be graded separately, possibly by different people, andreturned to you independently of each other.• For problems that require you to provide an algorithm, you must give a precise description ofthe algorithm, together with a proof of correctness and an analysis of its running time .You may use algorithms from class as subroutines. You may also use any facts that we provedin class or from the book.General guidelines for reductions. Model your solutions on the reduction of Maximum Match-ing to Maximum Flow given in class. To reduce problem B to problem A:1. Explain how to transform an instance IBof B into an instance IAof A.2. Explain how to transform a solution SAfor IAinto a solution SBfor IB.3. (large fraction of the points) Prove that SBis a correct solution for IB, provided that SAisa correct solution for IA. In case of optimization problems, it usually involves proving that thevalue of SAis equal to the value of SB. (Often, it is easier to prove ≥ and ≤ separately.)4. Analyze the efficiency of the resulting algorithm for problem B that uses your reduction andthe most suitable algorithm for problem A that we studied. Make sure that the running time isexpressed in terms of the length of IB, not IA.Exercises These should not be handed in, but the material they cover may appear on exams:1. (a) Reduce the maximum flow problem for a network with several source nodes (s1, . . . , sk) andseveral sink nodes (t1, . . . , t`) into the single-source single-sink maximum flow problem.(b) Some networks have capacity constraints on the flow amounts that can flow through theirintermediate vertices. Explain how the maximum flow problem for such a network can bereduced to Maximum Flow with edge capacity constraints only.12. Review Sections 7.6 (edge-disjoint paths) and 7.11 (project selection). These were covered with-out slides in class. To review Section 7.6, look at exercises 32 and 33.3. As usual, read, solve and check your answers on the solved exercises. They might be helpful forsome of the homework and exam problems.Problems to be handed inPage limits: The answer to each problem should fit in 2 pages (or one double-sided sheet) ofpaper. Longer answers will be penalized.1. (Vertex-disjoint paths) Section 7.6 of the textbook describes using the Ford-Fulkerson tofind edge-disjoint paths in a unweighted directed (and undirected) graphs. The number of edge-disjoint paths is a measure of how resistant a graph is to deletion of edges.Consider instead, an analogous notion that captures resistance to the deletion of vertices (thinkblocked intersections or failed routers). Two paths from s to t are vertex-disjoint if they passthrough disjoint (i.e. non-intersecting) sets of vertices. Note that vertex-disjointness impliesedge-disjointness, but not the other way around.• (Exercise, do not hand in) Give an example of paths that are edge-disjoint but not vertex-disjoint.In this problem, we consider the problem of finding a maximum-size vertex-disjoint collection ofpaths that connect two given vertices s and t.(a) Consider the greedy algorithm which works as follows: Given a directed, unweighted graph G = (V, E) and s, t ∈ V :1 Initialize set S to ∅2 while (there exists a path from s to t in G):3 do Find a path p from s to t in G (using, say, DFS).4 Add p to S5 Remove all intermediate vertices in p from V(along with corresponding edges from E).6 Output SGive an example of a graph for which the algorithm above will not always return amaximum-size set of vertex-disjoint paths.(b) Give a polynomial-time algorithm that takes a directed graph G along with vertex namess, t and outputs a maximum-size set of vertex-disjoint paths from s to t.(Hint: Reduce to the edge-disjoint paths problem in related graph G0which has two verticesfor every vertex of G.)(c) Prove that there exist k vertex-disjoint paths from s to t if and only if there is no set ofk − 1 vertices (not including s or t) whose deletion from G disconnects s from t.(Hint: Use the min-cut/max-flow