MA214 Algorithms and Data Structures
2023/24
Exercises 10
(Maximum flows and bipartite matching)
Exercise 10.1. Multiple-source, multiple-sink maximum flow problem 3 pts
A maximum-flow problem may have several sources and sinks, rather than just one of each. For example, a company might actually have a set of M factories {s1, . . . ,sM} and a set of N warehouses {t1, . . . , tN}, between which it wants to send goods. A possible such network is shown below.
(a) Extend the flow properties and definitions to the multiple-source, multiple-sink version of the problem.
(b) Describe how to solve the multiple-source, multiple sink version of the prob-lem by “reducing” it to the single-source, single-sink problem. That is, describe how to construct a single-source, single-sink flow network from a multiple-source, multiple-sink network so that a maximum flow in the former corresponds to a maximum flow in the latter, and vice versa.
(c) What is the time complexity of the algorithm proposed in the previous part?
Exercise 10.2. Maximum flow and bipartite matching 4 pts
An undirected graph G = (V, E) is bipartite if V can be partitioned into L and R = V − L such that all edges run between L and R. A matching in G is a subset of edges M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident with v. A maximum matching is a matching of maximum cardinality among all matchings of G.
Given a bipartite undirected graph G = (V, E), we can find a maximum matching of G by using flows as follows: We construct a flow network G′ = (V′, E′) with V′ = V ∪ {s, t}, source s and target t,
E′ = {(s, ℓ): ℓ ∈ L} ∪ {(r, t): r ∈ R} ∪ {(ℓ,r): (ℓ,r) ∈ G, ℓ ∈ L,r ∈ R} ,
and capacity 1 for each edge in E′. An integer-valued flow in G′
is a flow f such that f(u, v) is an integer for each edge (u, v) of G′. That is, in our scenario here, we have f(u, v) ∈ {0, 1}. A maximum flow f in G′
that is an integer-valued flow then gives a maximum matching M in G by including in M all edges (ℓ,r) with ℓ ∈ L and r ∈ R such that f(ℓ,r) = 1. We can find such flow by using the Edmonds–Karp algorithm.
Now, consider the following instance G = (V, E) of the maximum bipartite matching problem. Vertices on the left are in L, vertices on the right are in R = V − L.
(a) List all maximum matchings in this instance of the maximum bipartite matching problem.
(b) Use the construction described above to obtain a flow network for this instance of the matching problem.
(c) Pick any maximum matching found in (a), and give the corresponding flow in the flow network described in (b).
(d) Give all minimum cuts in the flow network constructed in (b). What is the capacity of each of these cuts? What does this tell you about the maximum flow in the flow network, and the cardinality of any maximum matching?
(e) Use the Edmonds–Karp algorithm on the flow network found in (b) to compute a maximum flow. Break ties among equal length augmenting paths lexicographi-cally. So any path that starts with u1 should be preferred over any path that starts with u3. Likewise, any path that starts with u2, v1 should be preferred over any path u2, v4. Re-draw the flow network and the residual network after each up-date.
Exercise 10.3. Integer-valued flows and maximum matching 3 pts
The setup in this exercise is the same as in the previous exercise. We will prove that, as claimed in the previous exercise, there is a one-to-one correspondence between integer-valued flows in the flow network G′ = (V′, E′) and matchings in the undirected bipar-tite graph G = (V, E).
(a) Show that if there is an integer-valued flow f of value |f| in G′, then there is a matching M in G of cardinality |M| = |f|.
(b) Show that if there is a matching M in G of cardinality |M|, then there is an integer-valued flow f in G′ of value |f| = |M|.