Weighted Perfect Matching in Bipartite Graphs

CMPT 405/705 Design & Analysis of Algorithms January 26, 2022

Plan for today Isolation Lemma Min weight perfect matching in bipartite graphs

Finding a minimum weight perfect matching in bipartite graphs

Min-weight perfect matchings Input: A bipartite graph G = (U,V,E) with weights on the edges. Goal: Find a perfect matching in G of minimal weight. We may assume that the graph is a complete bipartite graph, and missing edges have some huge weight. 1 A w(AE, BF, CG, DH) = 1+1+1+6 = 9 E 1 B F 2 2 w(AE, BG, CH, DF) = 1+2+2+2 = 7 1 C G This is the min-weight PM in the graph 2 D H 6

Min-weight perfect matchings Input: A bipartite graph G = (U,V,E) with |U| = |V| = n and integer weights wi,j>0 Goal (min value version): Output the weight of a min-weight perfect matching. A simplifying (though, admittedly, weird) assumption: Suppose that G has a unique perfect matching of minimal weight. Algorithm for the min value version: Define nxn matrix A over reals as Ai,j = 10wij 1. 2. Compute the determinant of A 3. Output the largest k such that det(A) is divisible by 10k Example, if det(A) = 4150100, then we output 2 (because 102 divides det(A))

Min-weight perfect matchings Recall: Given a nxn matrix A the determinant of A is Why can we assume that the min-weight PM is unique? ??? ? = ???? ? ??,? ? ? ?: ? [?] Similarly to last time, we use the one-to-one correspondence between perfect matchings in G and the terms in the sum. Each perfect matching M contributes to the sum ???,? ? = ?10??,? ?= 10 ???,? ?= 10?(?) Therefore , if the min-weight matching in G has weight k and it is unique, then it will contribute 10k, and all others will contribute a multiples of 10*10k. It is easy to find such minimal k (assuming that it is unique).

Min-weight perfect matchings Recall: Given a nxn matrix A the determinant of A is ??? ? = ???? ? ??,? ? ? ?: ? [?] 1 A E w(AE, BF, CG, DH) = 1+1+1+6 = 9 w(AE, BG, CF, DH) = 1+2+3+6=12 w(AE, BG, CH, DF) = 1+2+2+2 = 7 1 B F 2 3 2 1 C G E F G H 2 A 10 0 0 0 D H B 0 10 100 0 6 103 C 0 10 100 106 D 0 100 0 Det(A) = 10*10*10*106 - 10*100*103*106 + 10*100*100*100 = 109-1012+107

Isolation Lemma

Isolation Lemma Isolation Lemma: Fix a set U, let T1, T2 U. Fix an integer S. For each x U choose wx {1,2, S} uniformly independently. For each T define w(T) = ?x Twx. Then Pr[there is a unique Ti of minimum weight] > 1 |U|/S Note that the probability is independent of the number of sets (which is pretty surprising) For our applications, edges of G will be associated with the set U = E, and each set Ti will correspond to some perfect matching in G.

Isolation Lemma Isolation Lemma: Fix a set U, let T1, T2 U. Fix an integer S. For each x U choose wx {1,2, S} uniformly independently. For each T define w(T) = ?x Twx. Then Pr[there is a unique Ti of minimum weight] > 1 U/S Proof: Let Ex be the event that min{w(Ti) : x Ti} = min{w(Ti) : x Ti} Claim1: Pr[Ex] 1/S for all x U We prove claim 1 on the next slide Pr[there exists x such that Ex holds] |U|/S Claim2: If none of the Ex holds, then there is a unique Ti of min weight. Pr[there is a unique Ti of minimum weight] > 1-?x UPr[Ex]>1-|U|/S.

Isolation Lemma Let Ex be the event that min{w(Ti) : x Ti} = min{w(Ti) : x Ti} Claim1: Pr[Ex] <= 1/S for all x U Proof: Fix all random choices of w s except for wx. So we are only left with sampling the value of wx. Then A = min{w(Ti) : x Ti} is defined, and it is independent of wx. Also, denoted B = min{w(Ti\{x}) : x Ti} is defined and independent of wx. Furthermore, min{w(Ti) : x Ti} = B + wx. Hence, for min{w(Ti) : x Ti} = min{w(Ti) : x Ti} to happen, we need wx = A-B. Therefore, Pr[Ex] = Pr[wx = A-B] <= 1/S.

Isolation Lemma Let Ex be the event that min{w(Ti) : x Ti} = min{w(Ti) : x Ti} Claim2: If none of the Ex holds, then there is a unique Ti of min weight. Proof: We prove the contrapositive. Namely, we show that if the minimum is not unique, then Ex holds for some x U. Suppose toward contradiction that w(Ti) = w(Tj) for some i j have both minimum weight. In particular, there exists some x in one of the sets but not in the other. Let s say x Ti but x Tj. Since both are of min weight, it follows that min{w(Ti) : x Ti}=min{w(Ti) : x Ti}. Therefore, Ex holds.

Isolation Lemma Isolation Lemma: Fix a set U, let T1, T2 U. Fix an integer S. For each x U choose wx {1,2, S} uniformly independently. For each T define w(T) = ?x Twx. Then Pr[there is a unique Ti of minimum weight] > 1 U/S Proof: Let Ex be the event that min{w(Ti) : x Ti} = min{w(Ti) : x Ti} Claim1: Pr[Ex] <= 1/S for all x U. Claim2: If none of the Ex holds, then there is a unique Ti of min weight. Therefore, Pr[there is a unique Ti of minimum weight] > 1-?x MPr[Ex]>1-U/S.

Finding a minimum weight perfect matching in bipartite graphs

Min-weight perfect matchings Input: A bipartite graph G = (U,V,E) with |U| = |V| = n and integer weights we>0 Goal (min value version): Output the weight of a min-weight perfect matching. Algorithm: 1. For each edge e E choose a random re {1 S} 2. Define w*e = we (Sn+1) + re Define nxn matrix A over reals as Ai,j = 10w*ij 3. 4. Compute the determinant of A 5. Let k be maximal such that such that det(A) is divisible by 10k 6. Output round-down[ k/(Sn+1) ]

Min-weight perfect matchings Analysis: For each perfect matching M in G we have w*(M) = ?e Mw*e = (nS+1)?e Mwe + ?e Mre= (nS+1)w(M) + ?e Mre Note that ?e Mre<nS, and hence if we know w*(M), then w(M) = round-down[w*(M)/(nS+1)] Furthermore, by Isolation Lemma, if S=n3, then Pr[there is a unique PM w.r.t. w*] > 1 |E|/S>1-1/n. Therefore, with probability at least 1-|E|/S the algorithm will output the weight of the min-weight perfect matching in G.

Perfect matching in general graphs So far, we have discussed perfect matchings in bipartite graphs. In HW1 you will design an algorithm that finds a perfect matching in general (non-bipartite) graphs.

Questions? Comments?