Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

• Published on
10-Jul-2016

• View
214

2

Transcript

• Acta Informatica 15, 329-346 (1981)

9 Springer-Verlag 1981

Efficient Algorithms for Finding Maximum Matchings in Convex Bipartite Graphs and Related Problems

W. Lipski, Jr.*, and F.P. Preparata**

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA

Summary. A bipartite graph G = (A, B, E) is convex on the vertex set A if A can be ordered so that for each element b in the vertex set B the elements of A connected to b form an interval of A ; G is doubly convex if it is convex on both A and B. Letting [A[ = m and [B[ = n, in this paper we describe maximum matching algorithms which run in time O(m + hA(n)) on convex graphs (where A(n) is a very slowly growing function related to a functional inverse of Acker- mann 's function), and in time O(m + n) on doubly convex graphs. We also show that, given a maximum matching in a convex bipartite graph G, a correspond- ing maximum set of independent vertices can be found in time O(m+n). Finally, we briefly discuss some generalizations of convex bipartite graphs and some extensions of the previously discussed techniques to instances in scheduling theory.

1. Introduction

Matching problems constitute a traditionally important topic in combinatorics and operations research  and have been the object of extensive investigation. Particularly interesting is the problem of finding a maximum matching in a bipartite graph, which is stated as follows: Let G=(A, B,E) be an undirected bipartite graph, where A and B are sets of vertices, and E is a set of edges of the form (a, b) with aeA and beB. A subset M ~ E is a matching if no two edges in M are incident to the same vertex; M is of maximum cardinality (or simply, maximum) if it contains the maximum number of edges. As noted by Hopcroft and Karp , this problem has many applications, such as the chain decomposition of a partially ordered set, the determination of coset representatives in groups, etc. Hopcroft and Karp have also developed the best known algorithm for this problem.

* On leave from the Institute of Computer Science, Polish Academy of Sciences, P.O. Box 22, 00-901 Warsaw PKiN, Poland ** Also with the Departments of Electrical Engineering and of Computer Science

0001-5903/81/0015/0329/\$03.60

• 330 W. Lipski Jr. and F.P. Preparata

A special instance of the problem, with some industrial applications, was originally discussed by Glover  and referred to as matching in a convex bi- partite graph. A bipartite graph G is convex on A if an ordering" < " of the elements of A can be found so that for any beB and distinct a 1 and a 2 in A (with at

• Algorithms for Maximum Matchings in Bipartite Graphs 331

In words, element i of A is matched to an available element j of B whose corre- sponding interval ends the closest to i. The most time-consuming task of this algorithm is the formation of the set U and the associated determination of an element j e U with the smallest value of END[j] : for any given isA, it involves scanning all the elements of B connected to i. Thus the running time of this task is clearly O(IE[), as pointed out in .

In this paper we shall describe a considerably more efficient algorithm and investigate both specializations and generalizations of the original matching problem. Specifically, after considering (Sect. 2) the maximum matching problem in a convex bipartite graph, we shall analyze the further simplifications which are possible when the graph is doubly convex (Sect. 3), and the optimal time determination of the maximum set of independent vertices associated with a given maximum matching (Sect. 4). Finally (Sect. 5), we succinctly describe two generalizations of the convex matching problem and an extension of the techniques to weighted matching, which directly applies to the solution of a scheduling problem.

2. Maximum Matching in Convex Bipartite Graphs

Let G=(A, B, E) be a bipartite graph convex on A, with [A[=m and [B[=n. As before, A={1 ,2 . . . . . m} and B={1,2 . . . . . n}. For b~B, A(b)~_A denotes the set {a:(a,b)~E}; similarly, for aEA, B(a)~_B denotes the set {b:(a,b)eE}. Again, we assume that A is ordered so that, for each beB, A(b) is the interval [BEG[b], END[b]]. Notice that if the set A is not initially ordered so that the property of convexity is manifest, the bipartite graph G can be tested for possession of this property - and, if so, rearranged - in time O([E[ + m + n) by means of the Booth- Lueker algorithm . Clearly, if the graph is not given by the arrays BEG, END and those arrays have to be computed first, then no improvement is possible over Glover's O([E[) algorithm.

We begin by giving a generalization (and simpler proof) of Glover's rule.

Lemma 1. If (a, b)~E and A(b)~_A(c), Jor all c~B(a), then there is a maximum matching containing (a, b).

Proof. Suppose M is a maximum matching not containing (a, b). If a is unmatched then we may replace the edge of the matching incident to b with (a, b), similarly if b is unmatched. Suppose therefore that (a, c), (d, b)eM for some c~B, d~A. Since deA(b)~_A(c), it follows that (d,c)~E, and we may replace (a,c), (d,b) by (a, b), (d, c) (see Fig. 1). []

I I I I

d c l ' 1 I i

A B Fig. 1. To the proof of Lemma 1. Wiggly edges belong to the matching

• 332 W. Lipski Jr. and F.P. Preparata

In order to prove that Algorithm 0 correctly finds a maximum matching, let us denote by G~ the graph obtained from G by deleting 1 . . . . . i - 1 from A and M A T C H [ l ] . . . . . M A T C H [ i - 1 ] from B, together with the edges incident to all these vertices. Let M~ be the set of edges matched by Algorithm 0 to vertices 1, ..., i in A (we put M o = 13), and let Ai(b) and B~(a) be defined for G~ in the same way as A(b) and B(a) were defined for G. We say that M~ can be extended to a maximum matching of G if there is a maximum matching M of G containing M~; this means that M is the union of Mi and of a maximum matching of G~+ a-

Assume inductively that a < m and that M,_ 1 can be extended to a maximum matching of G. (This is trivially true for a = 1, since M 0 is empty and G o coincides with G.) We shall prove that M a can also be extended to a maximum matching of G. This is obviously true if Ba(a ) = t3, so assume that B,(a):I: O, whence Algo- rithm 0 chooses MATCH[a]=b+A. It is then sufficient to show that there is a maximum matching of G, containing (a, b). But this is immediate, since for any c in B,(a) we have A,(c)=[a, END[c]]; by line 4 of Algorithm 0, we have END[b] < END[c ] for any c + b in Ba(a), whence A~(b)~_ A,(c), and, by Lemma 1, the claim is established.

The efficiency of Algorithm 0 can be improved substantially by some additional preprocessing and the use of appropriate data structures. Indeed, the set U of unmatched vertices of B connected to a currently inspected vertex ieA can be stored on a priority queue, and if the elements of B are relabelled so that END  ==... __< END In], then the least element of the queue minimizes the value of END, as required by Glover's rule. Note that since the elements in the priority queue are integers in the range [1, n], we may employ the implementation of [3, 4], which allows each of the standard queue operations to be performed in time O(log log n) and uses space O(n). The content of the priority queue can be updated efficiently as i is increased by one, and it should be clear the whole algorithm can be implemented in time O(m+n loglogn) (note that all sorting operations which are needed involve n integers in the range [1, n], so they can be done in O(m + n) time by standard bucket sorting, see e.g. ).

However, as noted by Hopcroft [personal communication], a better algo- rithm is possible if we use an idea closely related to that employed in an efficient solution of the off-line MIN problem (see , p. 139). We shall now describe such an algorithm in some detail.

Assume END  __

• Algori thms for Max imum Matchings in Bipartite Graphs 333

This vertex i is chosen to be B E G [ j ] , i.e., the name of the set containing j, or F I N D ( j ) in the te rminology of the U N I O N - F I N D a lgor i thm (here B E G [ j ] refers to the current graph, with all previously ma tched vertices deleted). After i is ma tched to j, the graph is upda ted by deleting i, i.e., increasing B E G [ j ] to the next available value, for a l l j s B for which B E G [ j ] was equal to i. This means we take a union of A i and Asucctq and give this set the name S U C C [ i ] ( that is, we execute ( U N I O N ( i , S U C C [ i ] , S U C C [ i ] ) in the t e rminology of the U N I O N - F I N D algorithm), and then we upda te the links to reflect the fact that A~ has been deleted. This p rocedure m a y cause some j~B to become isolated, but this can easily be found out by checking whether F I N D ( j ) < E N D [ j ] . The whole algo- r i thm is summar ized below.

Algorithm 1. (Finding maximum matching in convex bipartite graph)

Input: BEG[I:n],END[I:n] E N D  < . . . < END [n]

Output: M A T C H [ l : n ] (MATCH [j] is the vertex in A matched to j~ B) 1 begin 2 for i := 1 to m do 3 begin A~: = r 4 PRED [ i ] := i - 1 5 SUCC [i] : = i + 1 6 e n d 7 SUCC:= 1, PRED[m+ l]:=m 8 for j: = 1 to n do ABEGtjj: =ABEGtJl W {j} 9 for j ,= 1 to n do (* find vertex to be matched to j ,)

10 begin i: = FIND(j) 11 if i < END [j] then MATCH [.j]: = i 12 else MATCH[j]:=A (* i unmatched ,) 13 UNION(i, SUCC[i], SUCCI-i]) 14 SUCC [PRED [i]]: = SUCC [i] 15 PRED[SUCC[i]] := PRED[i] 16 end 17 end

It can easily be p roven tha t Algor i thm 1 constructs exactly the same match ing as Algor i thm 0 does (if we assume the same labelling of vertices with E N D [ l ] < . . . < ENDI-n] in bo th cases, and if we choose the vertex j in line 4 of Algo- r i thm 0 to be the smallest e lement in U). Indeed, suppose inductively tha t for all j < j o bo th a lgor i thms either ma tch j to the same vertex in A or bo th leave j unmatched , and assume the ma in loop of Algor i thm 1 reaches J=Jo. Let us denote i o = FIND(jo) . If i o > E N D [Jo] then it is impossible to ma tch Jo wi thout violat ing the part ial match ing which was assumed to be chosen by bo th algori thms, and consequent ly bo th a lgor i thms will leave Jo unmatched. N o w suppose io < E N D [Jo] so tha t Algor i thm 1 ma tches jo to io. First notice that our inductive assumpt ion and the fact tha t F I N D ( j o ) = i o when Algor i thm 1 reaches J=Jo imply tha t all i < io connected to Jo are ma tched by bo th a lgor i thms to the same vertices J

• 334 W. Lipski Jr. and F.P. Preparata

the main loop in line 9 performs n FIND operations interleaved by n UNION operations, which requires O(nA (n)) steps, A (n) being an extremely slowly growing function related to a functional inverse of Ackermann's function (see Tarjan ). So we conclude that the running time of Algorithm 1 is O(m+nA(n)).

3. Maximum Matching in Doubly Convex Bipartite Graphs

As noted by Glover, the maximum matching problem becomes even simpler when the bipartite graph G is doubly convex, i.e., orderings of both A and B exist such that every A(b) is an interval of A and every B(a) is an interval of B.

As before, we assume that G be given as a bipartite graph convex on A, that is, as a set {: beB} representing intervals of A. In the rest of this section we shall also assume that the convex bipartite graph G under consideration is connected. In fact, it is very easy to find connected components of a convex bipartite graph. It is sufficient to scan vertices ieA in increasing order and to count the number of beginnings and the number of endings of intervals found up to vertex i. Each time these two counts coincide, a new connected com- ponent is found. With the elements of B labelled so that END  < . . . =< END [n], and with an additional array storing the same elements sorted by nondecreasing value of BEG (it can be formed in linear time by bucket sorting), the determination of connected components can be done in O(m + n) time.

A preliminary task is to test whether the set B can be reordered so that for each aeA the set B(a) be an interval of B. Pictorially, we may display G by means of a set of segments (Fig. 2 a): specifically, in the plane (x, y), we let the segment

i Left Boundary | \ Right

14~- ~ "t"~',l Boundary 12 i ~ 9

" ' " I I I I [ l I I ~ I

2[ ..ii I I+-.r_l-I I-! ,r,,.; l ,, l ,,.T d,_

2 4 6 8 10 12" (a)

t Bottom ~k Region

141,1- ~ Segments 1,:1

,2 b X ,2

6L- t:W::tdWC~To~ G 4- ~-~44-~-J25+4 Region 21- H - 4 - H 4 - ~ I I I segments 4

2 4 6 8 '0 12" (c)

, Midd,e "T/P/Region

i [ . 2 4 6 I0 12"

(b)

- Top _ L , I I I I ' - . ' eg'~176

- ! I I I I I I I ; P I I I r 11 i. 5 Middle

- , . , i l I l i l f l ! Reion ,/[ I i I [ 1 1 ] I : g _!.~.lJ.ll.lpij..~_._ _-[ I I r//II Regi~ -, , I i I I I i

2 4 6 8 i0 12"

(d) Fig. 2a-d. Different polygons corresponding to the same set of segments, a arbitrary order; b, e ordered by nonincreasing BEG; d ordered to exhibit double convexity

• Algorithms for Maximum Matchings in Bipartite Graphs 335

{(x,y): y=b, BEG[b] BEG[q ] and BEG[ q ] < . . . _< BEG[n] ; similarly, for some l

• 336 W. LipskiJr. and F.P. Preparata

The whole task is performed by the following algorithm, which computes for each segment j a parameter Y[j] denoting its order in the final arrangement. This algorithm also makes use of a special subroutine, which - if at all possible - partitions in linear time a sequence of integers into two nonincreasing subse- quences; for example (4, 6, 3, 5, 4) is partitioned into (4, 3) and (6, 5, 4). This simple subroutine is described formally in an appendix. Its additional feature, which is important for the correctness of our algorithm, is that the first term of the sequence is assigned to the first subsequence.

Algorithm 2. (Testing Jor double convexity of a connected convex bipartite graph)

Input: B E G [ I : n ] , E N D [ I : n ] The pairs (BEG[j ] , E N D [ J ] ) , j = 1 . . . . . n are in lexicographic increasing ordering

Output: Y[1 :n] Vertices j e B relabelled so that for 1 END [j m] then j m: = j

(* extract segments not in internal part of middle region *) 5 e : = E N D [ 1 ] , / : = 0 6 for j: = 1 to n do 7 if ( E N D [j] _-> e) and (j 4= 1) and (j 4=j m) then e: = E N D [j] 8 else begin l: = I + 1 9 SIll: = j

10 end 11 relabel the elements of B so that for 1 < j < n

(BEG[j] = BEG[J+ 1]) ~ (END [j] > E N D [ J + 1]) 12 reorder S [ 1 : l] so that for 1 < p < l

(BEG IS [p]] = BEG[SIp + 1]]) ~ (END [S[p]] > END[SIp + 1]]) 13 partition S[I : I ] into two subsequences SUB 1 [ l : l 1] and

SUB 2 [1:12], such that END [SUB 1 ] > . . . > END [SUB 1 [l 1 ]] and END[SUB2 ] > . . . > END[SUB 2]

14 kl:=k2:=k3:=l 15 f o r j : = l to n do (* determine Y[j] *) 16 if SUB 1 [k 1] = j then (...