CSCI 570 – Fall 2020 – HW9
Due November 4th 11:59pm 2020
1 Graded Problems
1. In the network below 1, the demand values are shown on vertices. Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Answer the following questions:
1. Describe how to reduce the circulation problem into a maximum flow problem.
2. Compute the maximum flow of the reduced problem.
3. Determine if there is a feasible circulation in the original graph.
Solution:
1. We first reduce the problem into a network circulation problem without lower bound. To do this, for each edge (u, v) ∈ E on the graph, we move lower bound l(u,v) from u to v. That is, the new du = du +l(u,v) and dv = dv −l(u,v), the new capacity for (u, v) is capacity(u, v) − l(u, v).
Then we reduce this into the maximum flow problem. To do this, we add two new nodes s and t. Then we link s to supplying nodes u with capacity du
Figure 1: Q1
1
Figure 2: Q2-1
Figure 3: Q2-3
and link demanding nodes to t with capacity dv. We run the maximum flow algorithm between s and t to see if the flow value equals to the sum of supplies.
2. 0
3. The circulation is not feasible because the maximum flow value is less than the sum of supplies(demands).
2. Whether the statement is True or False? Give your explanation.
1. For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum
flow that’s possible in the graph.
2. The problem of deciding whether a given flow f of a given flow network
G is maximum flow can be solved in linear time.
3. In any maximum flow there are no cycles that carry positive flow.(A cycle
< e1, ..., ek > carries positive flow iff f (e1) > 0, …, f (ek) > 0.)
4. Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the
total capacity leaving the source s.
Solution:
1. False. See the counterexample 2.
2. True. A flow is maximum if there is no s − t path in residual graph. It
can be solved in O(E).
3. False. See the counterexample 3.
4. True. Ford-Fulkerson takes every possible s − t path with the minimum
capacity of 2, since all the edge capacities are even integers. It requires at most C/2 iterations.
2
2 Practice Problems
3. Reading assignment: Kleinberg and Tardos, Chapter 7.
3