Discussion 8
1. You have successfully computed a maximum s-t flow f for a network G = (V; E) with integer edge capacities. Your boss now gives you another network G’ that is identical to G except that the capacity of exactly one edge is decreased by one. You are also explicitly given the edge whose capacity was changed. Describe how you can compute a maximum flow for G’ in O(|V| + |E|) time.
2. You need to transport iron-ore from the mine to the factory. We would like to determine how long it takes to transport. For this problem, you are given a graph representing the road network of cities, with a list of k of its vertices (t1, t2,…, tk) which are designated as factories, and one vertex S (the iron-ore mine) where all the ore is present.
We are also given the following:
● Road Capacities (amount of iron that can be transported per minute) for each road (edges) between the cities (vertices).
● Factory Capacities (amount of iron that can be received per minute) for each factory ( at t1, t2,…, tk)
● The amount of ore to be transported from the mine, C
Give a polynomial-time algorithm to determine the minimum amount of time necessary to transport and receive all the iron-ore at factories.
3. In a daring burglary, someone attempted to steal all the candy bars from the CS department. Luckily, he was quickly detected, and now, the course staff and students will have to keep him from escaping from campus. In order to do so, they can be deployed to monitor strategic routes.
More formally, we can think of the USC campus as a graph, in which the nodes are locations, and edges are pathways or corridors. One of the nodes (the instructor’s office) is the burglar’s starting point, and several nodes (the USC gates) are the escape points — if the burglar reaches any one of those, the candy bars will be gone forever. Students and staff can be placed to monitor the edges. As it is hard to hide that many candy bars, the burglar cannot pass by a monitored edge undetected.
Give an algorithm to compute the minimum number of students/staff needed to ensure that the burglar cannot reach any escape points undetected (you don’t need to output the corresponding assignment for students — the number is enough). As input, the algorithm takes the graph G = (V,E) representing the USC campus, the starting point s, and a set of escape points P ⊆ V . Prove that your algorithm is correct and runs in polynomial time.
4. We define a most vital edge of a network as an edge whose deletion causes the largest decrease in the maximum s-t-flow value. Let f be an arbitrary maximum s-t-flow. Either prove the following claims or show through counterexamples that they are false:
(a) A most vital edge is an edge e with the maximum value of c(e).
(b) A most vital edge is an edge e with the maximum value of f (e).
(c) A most vital edge is an edge e with the maximum value of f (e) among edges belonging to some minimum cut.
(d) An edge that does not belong to any minimum cut cannot be a most vital edge.
(e) A network can contain only one most vital edge.