Question? Leave a message!

Bipartite matching: max flow formulation

Bipartite matching: max flow formulation
Dr.AlexanderTyler Profile Pic
Published Date:21-07-2017
Website URL
7. NETWORK FLOW II bipartite matching ‣ disjoint paths ‣ extensions to max flow ‣ survey design ‣ airline scheduling ‣ image segmentation ‣ project selection ‣ Lecture slides by Kevin Wayne baseball elimination ‣ Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne Last updated on Dec 23, 2013, 3:31 PMSoviet rail network (1950s) "Free world" goal. Cut supplies (if cold war turns into real war). Reference: On the history of the transportation and maximum flow problems. Alexander Schrijver in Math Programming, 91: 3, 2002. Figure 2 2 From Harris and Ross 1955: Schematic diagram of the railway network of the Western So- vietUnionandEasternEuropeancountries, withamaximumflowofvalue163,000tonsfrom Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as ‘The bottleneck’.Max-flow and min-cut applications Max-flow and min-cut are widely applicable problem-solving model. Data mining. Open-pit mining. Bipartite matching. Network reliability. Baseball elimination. Image segmentation. Network connectivity. liver and hepatic vascularization segmentation Distributed computing. Security of statistical data. Egalitarian stable matching. Network intrusion detection. Multi-camera scene reconstruction. Sensor placement for homeland security. Many, many, more. 37. NETWORK FLOW II bipartite matching ‣ disjoint paths ‣ extensions to max flow ‣ survey design ‣ airline scheduling ‣ image segmentation ‣ project selection ‣ SECTION baseball elimination ‣Matching Def. Given an undirected graph G = (V, E) a subset of edges M ⊆ E is a matching if each node appears in at most one edge in M. Max matching. Given a graph, find a max cardinality matching. 5Bipartite matching Def. A graph G is bipartite if the nodes can be partitioned into two subsets L and R such that every edge connects a node in L to one in R. Bipartite matching. Given a bipartite graph G = (L ∪ R, E), find a max cardinality matching. 1' 1 2' 2 3' 3 4' 4 5' 5 L R matching: 1-2', 3-1', 4-5' 6Bipartite matching Def. A graph G is bipartite if the nodes can be partitioned into two subsets L and R such that every edge connects a node in L to one in R. Bipartite matching. Given a bipartite graph G = (L ∪ R, E), find a max cardinality matching. 1' 1 2' 2 3' 3 4' 4 5' 5 L R matching: 1-1', 2-2', 3-4', 4-5' 7Bipartite matching: max flow formulation Create digraph G' = (L ∪ R∪ s, t, E' ). Direct all edges from L to R, and assign infinite (or unit) capacity. Add source s, and unit capacity edges from s to each node in L. Add sink t, and unit capacity edges from each node in R to t. G' 1 1' ∞ 1 1 2 2' 3 3' s t 4 4' 5 5' L R 8Max flow formulation: proof of correctness Theorem. Max cardinality of a matching in G = value of max flow in G'. Pf. ≤ Given a max matching M of cardinality k. Consider flow f that sends 1 unit along each of k paths. f is a flow, and has value k. ▪ ∞ 1 1' 1 1' 1 1 2 2' 2 2' 3 3' s 3 3' t 4 4' 4 4' G 5 5' G' 5 5' 9Max flow formulation: proof of correctness Theorem. Max cardinality of a matching in G = value of max flow in G'. Pf. ≥ Let f be a max flow in G' of value k. Integrality theorem ⇒ k is integral and can assume f is 0-1. Consider M = set of edges from L to R with f (e) = 1. each node in L and R participates in at most one edge in M M = k: consider cut (L∪ s, R∪ t) ▪ ∞ 1 1' 1 1' 1 1 2 2' 2 2' 3 3' s 3 3' t 4 4' 4 4' 5 5' G' 5 5' G 10Perfect matching in a bipartite graph Def. Given a graph G = (V, E) a subset of edges M ⊆ E is a perfect matching if each node appears in exactly one edge in M. Q. When does a bipartite graph have a perfect matching? Structure of bipartite graphs with perfect matchings. Clearly we must have L = R . What other conditions are necessary? What conditions are sufficient? 11Perfect matching in a bipartite graph Notation. Let S be a subset of nodes, and let N(S) be the set of nodes adjacent to nodes in S. Observation. If a bipartite graph G = (L ∪ R, E) has a perfect matching, then N(S) ≥ S for all subsets S ⊆ L. Pf. Each node in S has to be matched to a different node in N(S). ▪ 1' 1 2' 2' 2 2 S = 2, 4, 5 N(S) = 2', 5' 3' 3 4' 4 4 5' 5' 5 5 no perfect matching 12Hall's theorem Theorem. Let G = (L ∪ R, E) be a bipartite graph with L = R . G has a perfect matching iff N(S) ≥ S for all subsets S ⊆ L. Pf. ⇒ This was the previous observation. 1' 1 2' 2' 2 2 S = 2, 4, 5 N(S) = 2', 5' 3' 3 4' 4 4 5' 5' 5 5 no perfect matching 13Proof of Hall's theorem Pf. ⇐ Suppose G does not have a perfect matching. Formulate as a max flow problem and let (A, B) be min cut in G'. By max-flow min-cut theorem, cap(A, B) L . Define L = L ∩ A, L = L ∩ B , R = R ∩ A. A B A cap(A, B) = L + R . B A Since min cut can't use ∞ edges: N(L ) ⊆ R . A A N(L ) ≤ R = cap(A, B) – L L – L = L . A A B B A Choose S = L . ▪ A 1 ∞ 1 ∞ G' 1' L = 2, 4, 5 A A L = 1, 3 B 2' ∞ 2 1 R = 2', 5' A 3' s N(L ) = 2', 5' A 1 4 3 4' 5 1 5' t 14Bipartite matching running time Theorem. The Ford-Fulkerson algorithm solves the bipartite matching problem in O(m n) time. Theorem. Hopcroft-Karp 1973 The bipartite matching problem can be 1/2 solved in O(m n ) time. SIAM J. COMPUT. Vol. 2, No. 4, December 1973 s/2 ANn ALGORITHM FOR MAXIMUM MATCHINGS IN BIPARTITE GRAPHS JOHN E. RICHARD M. AND KARP HOPCROFT" in a Abstract. The present paper shows how to construct a maximum matching bipartite graph with n vertices and m in a number of to edges computation steps proportional (m + n)x/. words, Key algorithm, algorithmic analysis, bipartite graphs, computational complexity, graphs, matching 1. Introduction. Suppose we are a array in which each cell given rectangular or set of is if no is designated as "occupied" "unoccupied". A cells independent ofthe lie an two cells in thesamerow orcolumn. Our object is to construct indepen- dent of cells maximum set occupied having cardinality. 15 the In one interpretation, rows of the array represent boys, and the columns and represent girls. Cell is occupied ifboy and j are compatible, we wish i,j girl to match a maximum number ofcompatible couples. the the and An alternate statement of problem is obtainedby representing rows the the vertices ofa The columns of array as bipartite graph. vertices corresponding is We to row and column j are joined by an edge ifand only if cell i,j occupied. a of then seek amaximum matching; i.e., maximumnumber edges,notwo ofwhich meet at a common vertex. This problem has a wide variety of applications These include (3, 4, 5). the determination of chain decompositions in partially ordered sets, of coset in of systems of distinct representatives, and of block- representatives groups, also occurs as a of sparse matrices. The problem triangular decompositions and the subroutine in the solution of the Hitchcock transportation problem, in determination ofwhether one tree is to a subtree of another. given isomorphic In view of this variety of applications, the computational complexity of the problem of finding a maximum matching in a bipartite graph is of interest. The best methods seem to require steps, where m is previous (1, 3, 4, 5) O(mn) the number of and n the number of vertices. The present method requires edges, only O((m steps. + n)x/) extend With this in We hope to our results to the nonbipartite case (cf. 2). the mind, all the results in 2 are derived for general graphs. The specialization to bipartite case occurs in 3. 2. anti paths. Let G (V, be a finite undirected Matchings augmenting E) the vertex set V edges, or isolated having graph loops, multiple vertices) (without and w is written A set and the set E. An edge incident with vertices v edge v, w. more than one in M. E is a ifno vertex v e V is incident with edge M matching a ofmaximum cardinality is called maximum matching. A matching M. vertex v is Wemake the definitions relative to a matching A following free is incident with no in M. if it edge Received the editors November 1972, and in revised form 23, 1973. This research by 14, April was in Science supported part by the National Foundation under Grants NSF GJ96, GPo25081 and GJ474. Department ofComputer Science, Cornell Ithaca, New York, 14850. University, Computer Science Department, University of California, California 94720. " Berkeley, 225Nonbipartite matching Nonbipartite matching. Given an undirected graph (not necessarily bipartite), find a matching of maximum cardinality. Structure of nonbipartite graphs is more complicated. But well-understood. Tutte-Berge, Edmonds-Galai 4 Blossom algorithm: O(n ). Edmonds 1965 1/2 Best known: O(m n ). Micali-Vazirani 1980, Vazirani 1994 COMBINATORICA 14 (i) (1994) 71-109 PATHS, TREES, AND FLOWERS COMBINATORICA Akad6miai Kiad6 - Springer-Verlag JACK EDMONDS A THEORY OF ALTERNATING PATHS AND BLOSSOMS FOR 1. Introduction. A graph G for purposes here is a finite set of elements PROVING CORRECTNESS OF THE O(v/-VE) GENERAL GRAPH called vertices and a finite set of elements called edges such that each edge MAXIMUM MATCHING ALGORITHM meets exactly two vertices, called the end-points of the edge. An edge is said to join its end-points. A matching in G is a subset of its edges such that no two meet the same VIJAY V. VAZIRANI 1 vertex. We describe an efficient algorithm for finding in a given graph a match- Received December 30, 1989 ing of maximum cardinality. This problem was posed and partly solved by Revised June 15, 1993 C. Berge; see Sections 3.7 and 3.8. Maximum matching is an aspect of a topic, treated in books on graph theory, which has developed during the last 75 years through the work of about a dozen authors. In particular, W. T. Tutte (8) characterized graphs which do not contain a perfect matching, or 1-factor as he calls it—that is a set of edges with exactly one member meeting each vertex. His theorem 1. Introduction prompted attempts at finding an efficient construction for perfect matchings. This and our two subsequent papers will be closely related to other work on Finding a maximum matching in a graph is a classical problem in the study of algorithms. In this paper we present new algorithmically relevant combinatorial the topic. Most of the known theorems follow nicely from our treatment, structure of matchings. This structure yields the first proof of correctness of the though for the most part they are not treated explicitly. Our treatment is general graph matching algorithm of Mieali and Vazirani 14; this is currently the independent and so no background reading is necessary. 16 most efficient known matching algorithm. Section 2 is a philosophical digression on the meaning of "efficient algorithm." Berge's theorem 2, which says that matching M in graph G is a maximum matching if and only if there are no augmenting paths w.r.t, it, gives an iterative Section 3 discusses ideas of Berge, Norman, and Rabin with a new proof of schema for finding a maximum matching in G, i.e. successively find augmenting Berge's theorem. Section 4 presents the bulk of the matching algorithm. paths. Finding augmenting paths is fairly easy in bipartite graphs; however, not Section 7 discusses some refinements of it. so in general graphs (see 13 for a detailed history of the problem). The first There is an extensive combinatorial-linear theory related on the one hand polynomial time algorithm (o(rvI4)) for general graph matching was given by to matchings in bipartite graphs and on the other hand to linear programming. Edmonds 4. In this paper, Edmonds introduced the notion of blossom (an odd It is surveyed, from different viewpoints, by Ford and Fulkerson in (5) and length alternating cycle), and showed that by "shrinking" blossoms, one can find augmenting path efficiently. In this seminal paper, Edmonds also introduced the by A. J. Hoffman in (6). They mention the problem of extending this relation- notion of a polynomial time algorithm. ship to non-bipartite graphs. Section 5 does this, or at least begins to do it. Over the years, faster implementations of Edmonds' algorithm were given by There, the Kônig theorem is generalized to a matching-duality theorem for several authors, including Whitzgall and Zahn 16, Balinski 1, Gabow 6, Lawler arbitrary graphs. This theorem immediately suggests a polyhedron which in a 12, and Kameda and Munro 10. In 1972, Hopcroft and Karp 9 proposed finding subsequent paper (4) is shown to be the convex hull of the vectors associated augmenting paths in phases; in each phase a maximal set of disjoint minimum length augmenting paths is found. They showed that only O(v/) phases are needed, with the matchings in a graph. as opposed to O(IV) iterations in the previously-mentioned schema. They also Maximum matching in non-bipartite graphs is at present unusual among presented an O(IEI) implementation of a phase in bipartite graphs, thereby giving combinatorial extremum problems in that it is very tractable and yet not of an O(Iv/llEi) matching algorithm for such graphs, and left the open problem of the "unimodular" type described in (5 and 6). 1 Partially supported by an NSF PYI Grant with matching funds from AT&; T Bell Labs at Cornell University Received November 22, 1963. Supported by the O.N.R. Logistics Project at Princeton AMS subject classification codes (1991): 05 C 70, 05 C 85 University and the A.R.O.D. Combinatorial Mathematics Project at N.B.S. 449 450 JACK EDMONDS Section 6 presents a certain invariance property of the dual to maximum matching. In paper (4), the algorithm is extended from maximizing the cardinality of a matching to maximizing for matchings the sum of weights attached to the edges. At another time, the algorithm will be extended from a capacity of one edge at each vertex to a capacity of d edges at vertex v . t t This paper is based on investigations begun with G. B. Dantzig while at the RAND Combinatorial Symposium during the summer of 1961. I am Historical significance (Jack Edmonds 1965) indebted to many people, at the Symposium and at the National Bureau of Standards, who have taken an interest in the matching problem. There has been much animated discussion on possible versions of an algorithm. 2. Digression. An explanation is due on the use of the words "efficient algorithm." First, what I present is a conceptual description of an algorithm and not a particular formalized algorithm or "code." For practical purposes computational details are vital. However, my purpose is only to show as attractively as I can that there is an efficient algorithm. According to the dictionary, "efficient" means "adequate in opera- tion or performance." This is roughly the meaning I want—in the sense that it is conceivable for maximum matching to have no efficient algorithm. Perhaps a better word is "good." I am claiming, as a mathematical result, the existence of a good algorithm for finding a maximum cardinality matching in a graph. There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph. The mathematical significance of this paper rests largely on the assumption that the two preceding sentences have mathematical meaning. I am not prepared to set up the machinery necessary to give them formal meaning, nor is the present context appropriate for doing this, but I should like to explain the idea a little further informally. It may be that since one is customarily 17 concerned with existence, convergence, finiteness, and so forth, one is not in- clined to take seriously the question of the existence of a better-than-finite algorithm. The relative cost, in time or whatever, of the various applications of a particular algorithm is a fairly clear notion, at least as a natural phenomenon. Presumably, the notion can be formalized. Here "algorithm" is used in the strict sense co mean the idealization of some physical machinery which gives a definite output, consisting of cost plus the desired result, for each member of a specified domain of inputs, the individual problems. The problem-domain of applicability for an algorithm often suggests for itself possible measures of size for the individual problems—for maximum matching, for example, the number of edges or the number of vertices in the k-regular bipartite graphs Dancing problem. Exclusive Ivy league party attended by n men and n women. Each man knows exactly k women; each woman knows exactly k men. Acquaintances are mutual. Is it possible to arrange a dance so that each woman dances with a different man that she knows? 2-regular bipartite graph Mathematical reformulation. Does every k-regular 1 1' bipartite graph have a perfect matching? 2 2' Ex. Boolean hypercube. 3 3' 4 4' women men 18k-regular bipartite graphs have perfect matchings Theorem. Every k-regular bipartite graph G has a perfect matching. Pf. Size of max matching = value of max flow in G'. Consider flow ⎧ 1/k if (u, v)∈ E ⎪ f (u,v) = 1 if u = s or v =t ⎨ ⎪ 0 otherwise ⎩ f is a flow in G' and its value = n ⇒ perfect matching. ▪ € 1 1/k 1' 1 1 1/k s t G' 2 2' 3 3' 4 4' a feasible flow f of value n 197. NETWORK FLOW II bipartite matching ‣ disjoint paths ‣ extensions to max flow ‣ survey design ‣ airline scheduling ‣ image segmentation ‣ project selection ‣ SECTION baseball elimination ‣