1 Removing Train Stations (50 points) = 2 We discussed in class how one of the original motivations for studying max-flow and min-cut comes from WWII, and in particular the questions of how much stuff can be moved from s to t along the rail network and what rail lines can we remove in order to destroy the ability to ship anything from s to t. Now suppose that instead of being able to remove rail lines, we have the ability to sabotage rail stations. Can we still find the best way to do this? More formally, suppose that we are given a directed graph G (V, E), two vertices s,t E V with (u, v) & E, and a function c:V\{s,t} + R0. As usual, |E| = m and [V] = n. We will call c(v) the cost of v. A feasible solution is a subset S CV \{s, t} so that there is no path from s to t in G S (the graph obtained from G by removing all vertices in S and all edges incident on at least one vertex in S). Your goal is to find the feasible solution S which has minimum cost, i.e., which minimizes Lues c(v). Design an algorithm for this problem which runs in O(mn) time. You may assume that m >n and that there is an algorithm for maximum flow which runs in O(mn) time (as we discussed in class: Orlin's algorithm). Prove running time and correctness. Hint: try to reduce this problem to a max-flow problem. 1 Removing Train Stations (50 points) = 2 We discussed in class how one of the original motivations for studying max-flow and min-cut comes from WWII, and in particular the questions of how much stuff can be moved from s to t along the rail network and what rail lines can we remove in order to destroy the ability to ship anything from s to t. Now suppose that instead of being able to remove rail lines, we have the ability to sabotage rail stations. Can we still find the best way to do this? More formally, suppose that we are given a directed graph G (V, E), two vertices s,t E V with (u, v) & E, and a function c:V\{s,t} + R0. As usual, |E| = m and [V] = n. We will call c(v) the cost of v. A feasible solution is a subset S CV \{s, t} so that there is no path from s to t in G S (the graph obtained from G by removing all vertices in S and all edges incident on at least one vertex in S). Your goal is to find the feasible solution S which has minimum cost, i.e., which minimizes Lues c(v). Design an algorithm for this problem which runs in O(mn) time. You may assume that m >n and that there is an algorithm for maximum flow which runs in O(mn) time (as we discussed in class: Orlin's algorithm). Prove running time and correctness. Hint: try to reduce this problem to a max-flow