DOC PREVIEW
MIT 6 854J - Lecture Notes

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms September 10, 2008 Lecture 3 Lecturer: Michel X. Goemans 1 Introduction Today we continue our discussion of maximum flows by introducing the fattest path augmenting algorithm, an improvement over the Ford-Fulkerson algorithm, to solve the max flow problem. We also discuss the minimum cost circulation problem. 2 Maximum Flow In a maximum flow problem, the goal is to find the greatest rate (flow) at which material can be sent from a source s to a sink t. Several problems can be modeled as a max-flow problem, including bipartite matching, which will be discussed today. We will also discuss flow decomposition and the fattest augmenting path algorithm. 2.1 Maximum Cardinality Matching in Bipartite Graphs A bipartite graph is a graph G = (V, E) whose vertex set V can be partitioned into two disjoint sets, A and B, such that every edge connects a vertex in A to one in B. A matching M is a subset of E such that the endpoints of all the edges in M are distinct. In other words, two edges in M cannot share a vertex. We are interested in solving the following problem: Given an undirected bipartite graph G = (V, E) where V = A ∪ B, find a matching M of maximum cardinality. We can formulate this maximum cardinality matching problem as a max-flow problem. To do that, c onsider the network shown in Figure 1. Figure 1: The figure on the left represents a matching in a bipartite graph. The figure on the right shows how the bipartite graph can be converted into a max-flow network by imposing a capacity of 1 on arcs out of s and into t. 3-1The network is constructed as follows: We orient each edge in G from A to B and assign them a capacity of 1 (any capacity greater than 1 works too). We also add two new vertices, s and t, and arcs from s to every vertex in A, and from every vertex in B to t. All the new arcs are given unit capacity. Theorem 1 Let G = (V, E) be a bipartite graph with vertex partition V = A ∪ B, and let G� = (V �, E�) be the capacitated network constructed as above. If M is a matching in G, then there is an integer-valued flow f in G� with value |f | = |M |. Conversely, if f is an integer-valued flow in G�, then t here is a matching M in G with cardinality |M| = |f|. Proof: Given M , define a flow f in G� as follows: if (u, v) ∈ M, then set f(s, u) = f (u, v) = f(v, t) = 1 and f(u, s) = f(v, u) = f(t, v) = −1. For all other edges (u, v) ∈ E�, let f (u, v) = 0. Each edge (u, v) ∈ M corresponds to 1 unit of flow in G� that traverses the path s → u → v → t. The paths in M have distinct vertices, aside from s and t. The net flow across the cut (A ∪ s : B ∪ t) is equal to |M|. We know that the net flow across any cut is the same, and equals the value of the flow. Thus, we can conclude that |M| = |f |. To prove the converse, let f be an integer-valued flow in G�. By flow conservation and the choice of capacities, the net flow in e ach arc must be -1, 0 or 1. Let M be the set of edges (u, v), with u ∈ A, v ∈ B for which f (u, v) = 1. It is easy to see, by flow conservation again, that M is indeed a matching and, using the same argument as before, that |M| = |f|. � Since all the capacities of this maximum flow problem are integer valued, we know that there always exists an integer-valued maximum flow, and therefore the theorem shows that this maximum flow formulation correc tly models the m aximum cardinality bipartite matching. 2.2 Flow Decomposition In an (raw) s-t flow, we have the following building blocks: • Unit flow on an s-t directed path. • Unit flow on a directed cycle. Any (raw) s-t flow can be written as a linear combination of these building blocks. Theorem 2 Any (raw) s-t flow r can be decomposed into at most m flows along either paths from s to t or cycles, where m is the number of edges in the network. More precisely, it can be decomposed into at most |{e : r(e) > 0}| ≤ m paths and cycles. Proof: By tracing back the flow on an edge e and tracing forward the flow on e, we either get an s-t path T , or a cycle T with r(e) > 0 for all e ∈ T . Denote the min flow on T by Δ(T ): Δ(T ) = min r(e). e∈T We want to decrease the flow on T such that at least one edge goes to 0 (by subtracting out Δ(T )), and keep doing that until there are no more edges with non-zero flows. More precisely, the following algorithm e xtracts at m ost m paths and cycles. (i) While there is a directed cycle C with positive flow: (a) Decrease the flow on this cycle by Δ(C) (b) Add this c ycle as an element of the flow decomposition (ii) (The set of arcs with positive flow now form an acyclic graph.) While there is a path P from s to t with positive flow: 3-2(a) Decrease the flow on this path by Δ(P ). (b) Add this path as an e leme nt of the flow decomposition. Each time we decrease the flow on a path or a cycle T , we zero out the flow on some edge. When we do this, the new raw flow is rnew(e) = r(e) − Δ(T ) if e ∈ T , or r(e) otherwise. Since there are |{e : r(e) > 0}| ≤ m edges with positive flow in the graph, there will be at most that number of decreases in the flow, and consequently, at most that number of paths or cycles in the flow decomposition. � 2.3 Fattest Augmenting Path Algorithm (Edmonds-Karp ’72) Flow decomposition is a key tool in the analysis of network flow algorithms, as we will illustrate now. As we saw in the last lecture, the Ford-Fulkerson algorithm for finding a maximum flow in a network may take exponential time, or even not terminate at all, if the augmenting path is not chosen appropriately. We proposed two spec ific choices of augmenting paths, both due to Edmonds and Karp, that provide a polynomial running time. One was the shortest augmenting path, the other was the fattest augmenting path or maximum-capacity augmenting path: the augmenting path that increases the flow the most. This is the variant we analyze now. For an augmenting s-t path P ∈ Gf , …


View Full Document

MIT 6 854J - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?