Graph Matchings II: Weighted Matchings

92weighted matchings in bipartite graphsfor each perfect matching M satisfies the constraints for K. MoreoverK is convex, so if it contains all the vertices of C, it contains all theirconvex combinations, and hence all of C.For the other direction, we show that an arbitrary vertex x of Kis contained within C. Using Fact 7.8, we use the fact that x is alsoan extreme point for K. (We can also use the fact that x is a basicfeasible solution, or that it is a vertex of the polytope, to prove thistheorem; we will add the former proof soon, the latter proof appearsin §7.3.)Let supp( x ) {e xe 0} be the support of this solution.We claim that supp( x ) is acyclic. Indeed, suppose not, and cycleC e1 , e2 , . . . , ek is contained within the support supp( x ). Since thegraph is bipartite, this is an even-length cycle. Defineε : mine supp( x )xe .Observe that for all ei C, xe i xe i 1 1, so xe i 1 ε. Andof course xe i ε, merely by the definition of ε. Now consider twosolutions x and x , wherexe i xe i ( 1)i εandxe i xe i ( 1)i ε.I.e., the two solutions add and subtract ε on alternate edges; thisensures that both the solutions stay within K. But then x 12 x 1 2 x , contradicting our that x is an extreme point.Therefore there are no cycles in supp( x ); this means the support is a forest. Consider a leaf vertex v in the support. Then, by theequality constraint at v, the single edge e supp( x ) leaving v musthave xe 1. But this edge e uv goes to another vertex u; becausex is in K, this vertex u cannot have other edges in supp( x ) withoutviolating its equality constraint. So u and v are a matched pair in x .Now remove u and v from consideration. We have introduced nocycles into the remainder of supp( x ), so we may perform the samestep inductively to show that x is the indicator of a perfect matching, and hence x C. This means all vertices of K are in C, whichproves C K, and completes the proof.This completes the proof that the polytope K PM(G) exactly capturesprecisely the perfect matchings in G, despite having such a simpledescription. Now, using the fact that the linear programmin{w · x x K PM(G) }can be solved in polynomial time, we get an efficient algorithm forfinding minimum-weight perfect matching in graphs.Figure 7.5: There cannot be a cyclein supp( x ), because this violates theassumption that x is an extreme point.

graph matchings ii: weighted matchingsTalk about duality and Konig’s theorem.7.2.3 A Proof via Basic Feasible SolutionHere is how to prove Theorem 7.12 using the notion of basic feasiblesolutions (bfs). Suppose x R E is a bfs: we now show that xe {0, 1} for all edges. By the definition of a bfs, there is a collectionof E tight linearly independent constraints that define x . Theseconstraints are of two kinds: the degree constraints e (v) xe 1 forsome subset S of vertices, and the non-negativity constraints xe 0for some subset E0 E be edges. (Hence we have E0 S E .)By reordering columns and rows, we can put the degree constraints at the top, and put all the edges in E0 at the end, to get thatx is defined by:"#"#C C01s x 0m s0 Iwhere C {0, 1}s s , C 0 {0, 1}(m s) s , and m E and s S .The edges in E0 have xe 0, so consider edges in E \ E0 . By the linearindependence of the constraints, we have C being non-singular, sox E\ E0 C 1 (1 C 0 x E0 ) C 1 1.By Cramer’s rule,xe det(C [1]i ).det(C )The numerator is an integer (since the entries of C are integers), soshowing det(C ) { 1} means that xe is an integer.Claim 7.13. Any k k-submatrix of C has determinant in { 1, 0, 1}.Proof. The proof is by induction on k; the base case is trivial. If thesubmatrix D has a column with a single 1, we can expand using thatentry, and use the inductive hypothesis. Else each column of D hastwo non-zeros. Recall that the columns of D correspond to someedges ED in E \ E0 , and the rows correspond to vertices SD in S—twonon-zeros in each column means each edge in ED has both endpointsin SD . Now if we sum rows for vertices in SD L would give the allones vector, as will summing up rows for vertices in SD R. (Here isthe only place we’re using bipartiteness.) In this case det( D ) 0.Using the claim and using the fact C is non-singular and hencedet(C ) cannot be zero, we get that the entries of xe are integers. Bythe structure of the LP, the only integers possible in a feasible solution are {0, 1} and the vector x corresponds to a matching.93

94another perspective: buyers and sellers7.2.4 Minimum-Weight MatchingsHow can we we find a minimum-weight (possibly non-perfect)matching in a bipartite graph G? If the edge weights are all nonnegative, the empty matching would be the solution—but what ifsome edge weights are negative? (In fact, that’s how we would find amaximum-weight matching–by negating all the weights.) As before,we can define the matching polytope for G asC Match(G) CH ({χ M M is a matching in G }).To write a compact LP that describes this polytope, we slightly modify our linear constraints as follows:K Match x R E xij 1 j R s.t. x ji 1 j L xi,j 0 i L i R i, j We leave it as an exercise to apply the techniques used in Theorem 7.12 to show that the vertices of K Match are matchings of G, andhence the following theorem:Theorem 7.14. For any bipartite graph G, K Match CH Match7.3Another Perspective: Buyers and sellersThe results of the previous section show that the bipartite perfectmatching polytope is integral, and hence the max-weight perfectmatching problem on bipartite graphs can be be solved by “simply” solving the LP and getting a vertex solution. But do we need ageneric linear program solver? Can we solve this problem faster? Inthis section, we develop (a variant of) the Hungarian algorithm thatfinds an optimal solutions using a “combinatorial” algorithm. Thisproof also shows that any vertex of the polytope K PM(G) is integral,and hence gives another proof of Theorem 7.12.7.3.1 The Setting: Buyers and ItemsConsider the setting with a set B with n buyers and another set I withn items, where buyer b has value vbi for item i. The goal is to find amax-value perfect matching, that matches each buyer to a distinctitem and maximizes the sum of the values obtained by this matching.Our algorithm will maintain a set of prices for items: each item iwill have price pi . Given a price vector p : ( p1 , . . . , pn ), define the

graph matchings ii: weighted matchingsutility of item i to buyer b to beubi ( p) : vbi pi .Intuitively, the utility measures how favorable it is for buyer b to buyitem i, since it factors in both the value and the price of the item.We say that buyer b prefers item i if item i gives the highest utilityto buyer b, among all items. Formally, buyer b B prefers item i atprices p if i arg maxi0 I ubi0 ( p). The utility of buyer b at prices p isthe utility of this preferred item:ub ( p) : max ubi ( p) max(vbi pi ).i Ii I(7.4)A buyer has at least one preferred item, and can have multiplepreferred items, since there can be ties. Given prices p, we build apreference graph H H ( p), where the vertices are buyers B on theleft, items I on the right, and where bi is an edge if buyer b prefersitem i at prices p. The two examples show preference graphs, wherethe second graph results from an increase in price of item 1. Flip thefigure.Theorem 7.15. For any price vector p , if the preference graph H ( p )contains a perfect matching M, then M is a max-value perfect matching.Proof. This proof uses weak linear programming duality. Indeed,recall the linear program we wrote for the bipartite perfect matchingproblem: we allow fractional matchings by assigning each edge bi afractional value xbi [0, 1].maximize vbi xbibinsubject to xbi 1 i xbi 1 bxbi 0 (b, i )b 1ni 1The perfect matching M is clearly feasible for this LP, so it remainsto show that it achieves the optimum. Indeed, we show this by exhibiting a feasible dual solution with value bi M vbi , the value of theprimal solution. Then by weak duality, both these solutions must beoptimal.The dual linear program is the following:minimizesubject tonni 1b 1 pi u bpi ub vbi bi95

96another perspective: buyers and sellers(Observe that u and p are unconstrained variables.) In fact, givenany settings of the pi variables, the ub variables that minimize theobjective function, while still satisfying the linear constraints, aregiven by ub : maxi I (vbi pi ), exactly matching (7.4). Hence, thedual program can then be rewritten as the following (non-linear,convex) program with no constraints:minp ( p1 ,.,pn ) p i u b ( p ).i Ib BConsider the dual solution given by the price vector p . Recall thatM is a perfect matching in the preference graph H ( p ), and let M(i )be the buyer matched to item i by it. Since u M(i) ( p) v M(i)i pi , thedual objective is pi ub ( p ) pi (v M(i)i pi ) i Ib Bi Ii Ivbi .bi MSince the primal and dual values are equal, the primal matching Mmust be optimal.Prices p ( p1 , . . . , pn ) are said to be market-clearing if each itemcan be assigned to some person who has maximum utility for it atthese prices, subject to the constraints of the problem. In our setting,having such prices are equivalent to having a perfect matching in thepreference graph. Hence, Theorem 7.15 shows that market-clearingprices give us an optimal matching, so our goal will be to find suchprices.7.3.2 The Hungarian algorithmThe “Hungarian” algorithm uses the buyers-and-sellers viewpointfrom the previous section. The idea of the algorithm is to iterativelychange item prices as long as they are not market-clearing, and thekey is to show that this procedure terminates. To make our proofseasier, we assume for now that all the values vbi are integers.The price-changing algorithm proceeds as follows:1. Initially, all items have price pi 0.The algorithm was named the Hungarian algorithm by Harold Kuhn, whobased his ideas on the works of JenöEgervary and Dénes König. Munkressubsequently showed that the algorithmwas in fact implementable in O(n3 ).Later, the algorithm was found to havebeen proposed even earlier by CarlGustav Jacobi, before 1851.2. In each iteration, build the current preference graph H ( p). If itcontains a perfect matching M, return it. Theorem 7.15 ensuresthat M is an optimal matching.3. Otherwise, by Hall’s theorem , there exists a set S of buyers suchthat ifN (S) : {i I b S, bi E( H ( p))}put Hall’s theorem as an exercise toKonigs theorem

graph matchings ii: weighted matchingsis the set of items preferred by at least one buyer in S, then N (S) S . (N (S) is the neighborhood of S in the preference graph.) Intuitively, we have many buyers trying to buy few items, so logically,the sellers of those items should raise their prices! The algorithmincreases the price of every item in N (S) by 1, and starts a newiteration by going back to step 2.That’s it. Running the algorithm on our running example gives theprices on the right.The only way the algorithm can stop is to produce an optimalmatching. So we must show it does stop, for which we use a “semiinvariant” argument. We keep track of the “potential”Φ( p) : p i u b ( p ),ibwhere pi are the current prices and ub ( p) maxi (vbi pi ) as above.This is just the dual value, and hence is is lower-bounded by theoptimal value of the dual program. (We assume the optimal value ofthe LP is finite, e.g., if all the input values are finite.) Then, it sufficesto prove the following:Lemma 7.16. Every time we increase the prices in N (S) by 1, the value of i pi b ub decreases by at least 1.Proof. The value of i pi increases by N (S) , because we increasethe price of each item i N (S) by 1. For each buyer b S, thevalue ub must decrease by 1, since all their preferred items had theirprices increased by 1, and all other items previously had utilitiesat least one lower than the original ub ( p). (Here, we used the factthat all values were integral.) Therefore, the value of the potential i pi b ub changes by N ( B) B 1.Hence the algorithm stops in finite time, and produces a maximumvalue perfect matching. By the arguments above ? we get yet another proof of integrality of the LP ? for the bipartite pefect matching problem. A few other remarks about the algorithm: In fact, one can get rid of the integrality assumption by raising theprices by the maximum amount possible for the above proof tostill go through, namely min ub ( p) max (vib pi ) .b Si 6 N (S)It can be shown Munkres? that this update rule makes the algorithm stop in only O(n3 ) iterations. Check! If all the values are non-negative, and we don’t like the utilities tobe negative, then we can do one of the following things: (a) when97

98a third algorithm: shortest augmenting pathsall the prices become non-zero, subtract the same amount from allof them to make the lowest price hit zero, or (b) choose S to be aminimal “consticted” set and raise the prices for N (S). This way,we can ensure that each buyer still has at least one item whichgives it nonngegative utility. (Exercise!) Suppose there are n buyers and a single item, with all non-negativevalues. (Imagine there are n 1 dummy items, with buyers having zero values for them.) The above algorithm behaves like theusual ascending-price English or Vickery auction, where pricesare raised until only one bidder remains. Indeed, the final pricefor the “real” item will be such that the second-highest bidder isindifferent between it and a dummy item.This is a more general phenomenon: indeed, even in the settingwith multiple items, the final prices are those produced by theVickery-Clarke-Groves truthful mechanism, at least if we use theversion of the algorithm that raises prices on minimal constrictedsets. The truthfulness of the mechanism means there is no incentive for buyers to unilaterally lie about their values for items. See,e.g., 1 for the rich connection of matching algorithms to auctiontheory and (algorithmic) mechanism design.Check about negative values, they don’t seem to matter at all,as long as everything is finite. What about max-weight maximummatching: we can always convert the graph, but does the algorithmwork out of the box?This proof shows that for any setting of values, there is an optimalinteger solution to the linear programmax{v · x x K LP(G) }.This implies that every vertex x of the polytope K LP(G) is integral—indeed, the definition of vertex means x is the unique solution to thelinear program for some values v, and our proof just produced anintegral matching that is the optimal solution. Hence, we get anotherproof of Theorem 7.12, this time using the notion of vertices insteadof extreme points.7.4A Third Algorithm: Shortest Augmenting PathsLet us now see yet another algorithm for solving weighted matchingproblems in bipartite graphs. For now, we switch from maximumweight matchings to minimum-weight matchings, because they areconceptually cleaner to explain here. Of course, the two problems areequivalent, since we can always negate edges. Check details.1

graph matchings ii: weighted matchingsIn fact, we solve a min-cost max-flow problem here: given an flownetwork with terminals s and t, edge capacities ue , and also edgecosts/weights we , find an s-t flow with maximum flow value, andwhose total cost/weight is the least among all such flows. (Moreover,if the capacities are integers, the flow we find will also have integerflow values on all edges.) Casting the maximum-cardinality bipartitematching problem as a integer max-flow problem, as in §blah givesus a minimum-weight bipartite matching.This algorithm uses an augmenting path subroutine, much likethe algorithm of Ford and Fulkerson. The subroutine, which takes ina matching M and returns one of size M 1, is presented below.Then, we can start with the empty matching and call this subroutineuntil we get a maximum matching.Let the original bipartite graph be G. Construct the directed graphG M as follows: For each edge e M, insert that edge directed fromright to left, with weight we . For each edge e G \ M, insert thatedge directed from left to right, with weight we . Then, compute theshortest path P that starts from the left and ends on the right, andreturn M 4 P. It is easy to see that M 4 P is a matching of size M 1, and has total weight equal to the sum of the weights of M and P.Call a matching M an extreme matching if M has minimumweight among all matchings of size M . The main idea is to showthat the above subroutine preserves extremity, so that the final matching must be extreme and therefore optimal.Theorem 7.17. If M is an extreme matching, then so is M 4 P.Proof. Suppose that M is extreme. We will show that there existsan augmenting path P such that M 4 P is extreme. Then, since thealgorithm finds the shortest augmenting path, it will find a path thatis no longer than P, so the returned matching must also be extreme.Consider an extreme matching M0 of size M 1. Then, the edgesin M 4 M0 are composed of disjoint paths and cycles. Since M 4 M0has more edges in M0 than edges in M, there is some path P M 4M0 with one more edge in M0 than in M. This path necessarily startsand ends on opposite sides, so we can direct it to start from the leftand end on the right. We know that M0 P M P 1, whichmeans that M \ P and M0 \ P must have equal size. The total weight ofM\ P and M0 \ P must be the same, since otherwise, we can swap thetwo matchings and improve one of M and M0 . Therefore, M 4 P ( M0 P) ( M\ P) has the same weight as M0 and is extreme.Note that the formulation of G M is exactly the graph constructedif we represent the minimum matching problem as a min-cost flow.Indeed, the previous theorem can be generalized to a very similarstatement for the augmenting path algorithm for min-cost flows.99

100perfect matchings in general graphs7.5Perfect Matchings in General GraphsInterestingly, Theorem 7.12 is false for non-bipartite graphs. Indeed,consider graph K3 which consists of a single 3-cycle: this graph hasno perfect matching, but setting xe 1/2 for each edge satisfies all theconstraints. This suggests that the linear constraints defining K PM(G)are not enough, and we need to add more constraints to capture theconvex hull of perfect matchings in general graphs.In situations like this, it is instructive to look at the counterexample, to see what constraints must be satisfied by any integersolution, but are violated by this fractional solution. For a set of vertices S V, let (S) denote the edges leaving S. Here is one such setof constraints: xe 1 S V such that S is odd,.e (S)These constraints say: the vertices belonging to a set S V of oddsize cannot be perfectly matched within themselves, and at least oneedge from any perfect matching must leave S. Indeed, this constraintwould be violated by S V (K3 ) in the example above.Adding these odd

c x,c x, and hc, xito denote the inner-product between vectors c and x. graph matchings ii: weighted matchings 89 Definition 7.6 (Vertex). Given a polyhedron K Rn, a point x 2K is a vertex of K if there exists an vector c 2Rn such that c x c y for all y 2K y 6 x.