Maximum Flows and Minimum Cuts

Prev: All-Pairs Shortest Paths Next: Applications of Flows and Cuts

Exercises

0.

Suppose you are given a directed graph $G=(V,E)$, two vertices s and t, a capacity function $c:E\to {\mathbb{R}}_{+}$, and a second function $f:E\to \mathbb{R}$. Describe an algorithm to determine whether $f$ is a maximum $(s,t)$-flow in $G$.

1.

Let $f$ and $f^{\prime }$ be two feasible $(s,t)$-flows in a flow network $G$, such that $|f^{\prime }|>|f|$. Prove that there is a feasible $(s,t)$-flow with value $|f^{\prime }|-|f|$ in the residual network $G_f$.

2.

Let $u\to v$ be an arbitrary edge in an arbitrary flow network G. Prove that if there is a minimum $(s,t)$-cut $(S,T)$ such that $u\in S$ and $v\in T$, then there is no minimum cut $(S^{\prime },T^{\prime })$ such that $u\in T^{\prime }$ and $v\in S^{\prime }$.

3.

Let $(S,T)$ and $(S^{\prime },T^{\prime })$ be minimum $(s,t)$-cuts in some flow network $G$. Prove that $(S\cap S^{\prime },T\cup T^{\prime })$ and $(S\cup S^{\prime },T\cap T^{\prime })$ are also minimum $(s,t)$-cuts in $G$.

4.

Let G be a flow network that contains an opposing pair of edges $u\to v$ and $v\to u$, both with positive capacity. Let $G^{\prime }$ be the flow network obtained from G by decreasing the capacities of both of these edges by min{c($u\to v$), c($v\to u$)}. In other words: • If c($u\to v$) > c($v\to u$), change the capacity of $u\to v$ to c($u\to v$) − c($v\to u$) and delete $v\to u$. • If c($u\to v$) < c($v\to u$), change the capacity of $v\to u$ to c($v\to u$) − c($u\to v$) and delete $u\to v$. • Finally, if c($u\to v$) = c($v\to u$), delete both $u\to v$ and $v\to u$. (a) Prove that every maximum (s, t)-flow in $G^{\prime }$ is also a maximum (s, t)-flow in G. (Thus, by simplifying every opposing pair of edges in G, we obtain a new reduced flow network with the same maximum flow value as G.) (b) Prove that every minimum (s, t)-cut in G is also a minimum (s, t)-cut in $G^{\prime }$ and vice versa. (c) Prove that there is at least one maximum (s, t)-flow in G that is not a maximum (s, t)-flow in $G^{\prime }$.

5.

(a) Describe an efficient algorithm to determine whether a given flow network contains a unique maximum (s, t)-flow. (b) Describe an efficient algorithm to determine whether a given flow network contains a unique minimum (s, t)-cut. (c) Describe a flow network that contains a unique maximum (s, t)-flow but does not contain a unique minimum (s, t)-cut. (d) Describe a flow network that contains a unique minimum (s, t)-cut but does not contain a unique maximum (s, t)-flow.

6.

An (s, t)-flow in a network G is acyclic if there are no directed cycles where every edge has a positive flow value; that is, the subgraph of edges with positive flow value is a dag. (a) Describe and analyze an algorithm to compute an acyclic maximum (s, t)-flow in a given flow network. Your algorithm should have the same asymptotic running time as Ford-Fulkerson. (b) Describe and analyze an algorithm to determine whether every maximum (s, t)-flow in a given flow network is acyclic.

7.

Let $G=(V,E)$ be a flow network in which every edge has capacity 1 and the shortest-path distance from s to t is at least d. (a) Prove that the value of the maximum (s, t)-flow is at most E/d. (b) Now suppose that G is simple, meaning that for all vertices u and v, there is at most one edge from u to v. (Flow networks can have parallel edges.) Prove that the value of the maximum $(s,t)$-flow is at most $O(V^2/d^2)$. [Hint: How many nodes are in the average level of a BFS tree rooted at $s$?]

8.

Suppose we are given a flow network $G=(V,E)$ in which every edge has capacity 1, together with an integer k. Describe and analyze an algorithm to identify k edges in G such that after deleting those k edges, the value of the maximum (s, t)-flow in the remaining graph is as small as possible.

9.

The analysis in our proof of the Flow Decomposition Theorem can be tightened. Let $G=(V,E)$ be an arbitrary flow network, and let f be an arbitrary (s, t)-flow in G. (a) Prove that if | f | = 0, then f is the weighted sum of at most E − V + 1 directed cycles, where f (e) > 0 for every edge e in each of these cycles. (b) Prove that if | f | > 0, then f is the weighted sum of at most E − V + 2 directed paths and directed cycles, where f (e) > 0 for every edge e in each of these paths and cycles. (c) Prove that both of the previous upper bounds are tight: There are graphs in which some circulations cannot be decomposed into less than E − V +1 cycles, and some flows cannot be decomposed into less than E − V + 2 paths and cycles. [Hint: This is easy.]

10.

Our observation that any linear combination of (s, t)-flows is itself an (s, t)flow implies that the set of all (not necessarily feasible) (s, t)-flows in any graph actually define a real vector space, which we can call the flow space of the graph. (a) Prove that the flow space of any connected graph $G=(V,E)$ has dimension E − V + 2. (b) Let T be any spanning tree of G. Prove that the following collection of paths and cycles define a basis for the flow space: • The unique path in T from s to t; • The unique cycle in T \cup {e}, for every edge e \notin T. (c) Let T be any spanning tree of G, and let F be the forest obtained by deleting any single edge in T. Prove that the following collection of paths and cycles define a basis for the flow space: • The unique path in F \cup {e} from s to t, for every edge e \notin F that has one endpoint in each component of F; • The unique cycle in F \cup {e}, for every edge e \notin F with both endpoints in the same component of F. (d) Prove or disprove the following claim: Every connected flow network has a flow basis that consists entirely of simple paths from s to t.

11.

Cuts are sometimes defined as subsets of the edges of the graph, instead of as partitions of its vertices. In this problem, you will prove that these two definitions are almost equivalent. We say that a subset $X$ of directed edges separates $s$ and $t$ if every directed path from $s$ to $t$ contains at least one edge in $X$. For any subset $S$ of vertices, let

$$\delta (S):=\{u\to v\mid u\in S,v\notin S\}.$$

(a) Prove that if (S, T) is an (s, t)-cut, then δS separates s and t. (b) Let X be an arbitrary subset of edges that separates s and t. Prove that there is an (s, t)-cut (S, T) such that δS \subseteq X. (c) Let X be a minimal subset of edges that separates s and t. (Such a set of edges is sometimes called a bond.) Prove that there is an (s, t)-cut (S, T) such that δS = X.

12.

Suppose instead of capacities, we consider networks where each edge $u\to v$ has a non-negative demand d($u\to v$). Now an (s, t)-flow f is feasible if and only if f ($u\to v$) \ge d($u\to v$) for every edge $u\to v$. (Feasible flow values can now be arbitrarily large.) A natural problem in this setting is to find a feasible (s, t)-flow of minimum value. (a) Describe an efficient algorithm to compute a feasible (s, t)-flow, given the graph, the demand function, and the vertices s and t as input. [Hint: Find a flow that is non-zero everywhere, and then scale it up to make it feasible.] (b) Suppose you have access to a subroutine MaxFlow that computes maximum flows in networks with edge capacities. Describe an efficient algorithm to compute a minimum flow in a given network with edge demands; your algorithm should call MaxFlow exactly once. (c) State and prove an analogue of the max-flow min-cut theorem for this setting. (Do minimum flows correspond to maximum cuts?)

13.

For any flow network G and any vertices u and v, let bottleneckG (u, v) denote the maximum, over all paths π in G from u to v, of the minimum-capacity edge along π. (a) Describe and analyze an algorithm to compute bottleneckG (s, t) in $O(E\log V)$ time. This is the amount of flow that the Edmonds-Karp fattest-augmenting-paths algorithm pushes in the first iteration. (b) Now suppose the flow network G is undirected; equivalently, suppose c($u\to v$) = c($v\to u$) for every pair of vertices u and v. Describe and analyze an algorithm to compute bottleneckG (s, t) in $O(V+E)$ time. [Hint: Find the median edge capacity.] Why doesn’t this speedup work for directed graphs? (c) Again, suppose the flow network G is undirected. Describe and analyze an algorithm to construct a spanning tree T of G such that bottleneck T (u, v) = bottleneckG (u, v) for all vertices u and v. (Edges in T inherit their capacities from G.) For full credit, your algorithm should run in $O(E)$ time.

14.

Suppose you are given a flow network G with integer edge capacities and an integer maximum flow $f^{\ast }$ in G. Describe algorithms for the following operations: (a) Increment(e): Increase the capacity of edge e by 1 and update the maximum flow. (b) Decrement(e): Decrease the capacity of edge e by 1 and update the maximum flow. Both algorithms should modify f ∗ so that it is still a maximum flow, more quickly than recomputing a maximum flow from scratch.

15.

Let G be a network with integer edge capacities. An edge in G is upperbinding if increasing its capacity by 1 also increases the value of the maximum flow in G. Similarly, an edge is lower-binding if decreasing its capacity by 1 also decreases the value of the maximum flow in G. (a) Does every network G have at least one upper-binding edge? Prove your answer is correct. (b) Does every network G have at least one lower-binding edge? Prove your answer is correct. (c) Describe an algorithm to find all upper-binding edges in G, given both G and a maximum flow in G as input, in $O(E)$ time. (d) Describe an algorithm to find all lower-binding edges in G, given both G and a maximum flow in G as input, in $O(EV)$ time.

16.

A given flow network G may have more than one minimum (s, t)-cut. Let’s define the best minimum (s, t)-cut to be any minimum cut (S, T) with the smallest number of edges crossing from S to T. (a) Describe an efficient algorithm to find the best minimum (s, t)-cut when the capacities are integers. (b) Describe an efficient algorithm to find the best minimum (s, t)-cut for arbitrary edge capacities. (c) Describe an efficient algorithm to determine whether a given flow network contains a unique best minimum (s, t)-cut.

17.

A new assistant professor, teaching maximum flows for the first time, suggests the following greedy modification to the generic Ford-Fulkerson augmenting path algorithm. Instead of maintaining a residual graph, just5 reduce the capacity of edges along the augmenting path! In particular, whenever we saturate an edge, just remove it from the graph. Who needs all that residual graph nonsense?

GreedyFlow(G, c, s, t):
for every edge e in G
f
(e) ← 0
while there is a path from s to t
π ← an arbitrary path from s to t
F ← minimum capacity of any edge in π
for every edge e in π
f
(e) ← f
(e) + F
if c(e) = F
remove e from G
else
c(e) ← c(e) − F
return f

(a) Show that GreedyFlow does not always compute a maximum flow. (b) Show that GreedyFlow is not even guaranteed to compute a good approximation to the maximum flow. That is, for any constant α > 1, there is a flow network G such that the value of the maximum flow is more than α times the value of the flow computed by GreedyFlow. [Hint: Assume that GreedyFlow chooses the worst possible path π at each iteration.]

18.

In 1980 Maurice Queyranne published an example of a flow network, shown below, where Edmonds and Karp’s “fattest path” heuristic does not halt. As in Zwick’s bad example for p the original Ford-Fulkerson algorithm, φ denotes the inverse golden ratio (5 − 1)/2. The three vertical edges play essentially the same role as the horizontal edges in Zwick’s example. The adverb just is almost always subconscious shorthand for “I’m too lazy to figure out the details, but you should believe me anyway”, or more succinctly, “This is probably wrong.” See also merely, simply, clearly, and obviously. a b ϕ/2 c d ϕ/2 ϕ ϕ/2 ϕ e ϕ/2 f g h ϕ/2 (a) Show that the following infinite sequence of path augmentations is a valid execution of the Edmonds-Karp “fattest path” algorithm. (See the bottom of Figure 10.12.)

QueyranneFatPaths:
for i ← 1 to ∞
push φ 3i−2 units of flow along s -> a ->  f  ->  g  ->  b -> h -> c  -> d  ->  t
push φ 3i−1 units of flow along s ->  f  -> a ->  b ->  g  -> h -> c  ->  t
push φ 3i units of flow along s -> e ->  f  -> a ->  g  ->  b -> c  -> h ->  t

(b) Describe a sequence of $O(1) path augmentations that yields a maximum flow in Queyranne’s network.

19.

An (s, t)-series-parallel graph is a directed acyclic graph with two distinguished vertices s and t and with one of the following structures: • Base case: A single directed edge from s to t. • Series: The union of an (s, u)-series-parallel graph and a (u, t)-seriesparallel graph that share a common vertex u but no other vertices or edges. • Parallel: The union of two smaller (s, t)-series-parallel graphs with the same source s and target t, but with no other vertices or edges in common. Every (s, t)-series-parallel graph G can be represented by a decomposition tree, which is a binary tree with three types of nodes: leaves (which corresponding to edges in G), series nodes (which correspond to vertices other than s and t), and parallel nodes. The same series-parallel graph could be represented by many different decomposition trees. (a) Suppose you are given a directed graph G with two special vertices s and t. Describe and analyze an algorithm that either builds a decomposition tree for G or correctly reports that G is not (s, t)-series-parallel. [Hint: Build the tree from the bottom up.] l g a b e f i h e c d l j k a d f b c j i g k h (b) Describe and analyze an algorithm to compute a maximum (s, t)-flow in a given (s, t)-series-parallel flow network with arbitrary edge capacities. [Hint: In light of part (a), you can assume that you are actually given the decomposition tree. First compute the maximum-flow value, then compute an actual maximum flow.]

20.

We can speed up the Edmonds-Karp “fattest path” algorithm, at least for networks with small integer capacities, by relaxing our requirements for the next augmenting path. Instead of finding the augmenting path with maximum bottleneck capacity, we find a path whose bottleneck capacity is at least half of maximum, using the following capacity scaling algorithm. (This algorithm was actually proposed by Edmonds and Karp.) Assume all the edge capacities are positive integers less than $U=2k$ for some integer k. The scaling algorithm maintains a bottleneck threshold ∆; initially, we set ∆ ← U. In each phase, the algorithm augments along paths from s to t in which every edge has residual capacity at least ∆. When there is no such path, the phase ends, we set ∆ ← b∆/2c, and the next phase begins. The algorithm ends when ∆ = 0. (a) How many phases will this algorithm execute in the worst case? (b) Let f be the flow at the end of a phase for a particular value of ∆. Prove that the capacity of a minimum cut in the residual graph G f is at most (c) Prove that in each phase of the scaling algorithm, there are at most 2E augmentations. (d) What is the overall running time of the capacity scaling algorithm?

Prev: All-Pairs Shortest Paths Next: Applications of Flows and Cuts