An improved approximation lower bound for finding almost stable maximum matchings

  • Published on

  • View

  • Download


Information Processing Letters 109 (2009) 10361040Contents lists available at ScienceDirectcecom/A unmK i b,a G oto 606b A machi,aArReReAcAvCoKeApThApPoproblaveBirs minithinlists are of length at most 3. In this paper, we improve this constant to n for any1.GaAnwisopThmnotoinGablalprcl*iw(S.00doywords:proximation algorithmse stable marriage problemproximation ratiolynomial-time reduction > 0, where n is the number of men in an input. 2009 Elsevier B.V. All rights reserved.IntroductionThe stable marriage problem (SM for short), introduced byle and Shapley [3] (see also [7]), is dened as follows:instance consists of the same number n of men andomen and each persons preference list. A preference lista totally-ordered list that includes all members of theposite sex in accordance with the owners preference.e problem requires to nd a stable matching, a perfectatching M between men and women in which there ispair of man m and woman w , that are not matchedgether in M but each prefers the other to ones partnerM . Such a pair (m,w) is called a blocking pair for M .le and Shapley [3] proved that there is at least one sta-e matching in any instance, and proposed an O (n2)-timegorithm to nd one.One possible extension of SM is to allow incompleteeference lists (SMI for short); namely, each person in-udes a subset of the members of the opposite sex in theCorresponding author.E-mail addresses: (K. Hamada), (K. Iwama), list. Those who are included in a person pspreference list are said to be acceptable to p. Now a match-ing is dened as a set of disjoint pairs of mutually accept-able man and woman, and hence is not necessarily perfect.Accordingly, the denition of a blocking pair is extended asfollows: A mutually acceptable pair of man m and womanw is a blocking pair for a matching M if (i) m and w arenot matched together in M , (ii) either m is single or prefersw to his partner in M , and (iii) either w is single or prefersm to her partner in M . There can be many stable match-ings for one instance, but all stable matchings are of thesame size [6].However, if we do not care about the stability, therecan be larger matchings in general. So, we may some-times want to obtain larger matchings by sacricing thestability, but even in such a case, it is still natural to seeka matching which is as stable as possible. Related to thisconsideration, Bir et al. [2] dened the following opti-mization problem, called MAX SIZE MIN BP SMI: Givenan SMI instance, nd a matching that minimizes the num-ber of blocking pairs among all the maximum cardinalitymatchings. For integers p and q, MAX SIZE MIN BP (p,q)-SMI is the restriction of MAX SIZE MIN BP SMI so thateach mans preference list is of length at most p, and each20-0190/$ see front matter 2009 Elsevier B.V. All rights reserved.i:10.1016/j.ipl.2009.06.008Information Prowww.elsevier.n improved approximation lower boaximum matchingsoki Hamada a, Kazuo Iwama a, Shuichi Miyazakraduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kycademic Center for Computing and Media Studies, Kyoto University, Yoshida-Honr t i c l e i n f o a b s t r a c tticle history:ceived 12 February 2009ceived in revised form 1 June 2009cepted 19 June 2009ailable online 23 June 2009mmunicated by F.Y.L. ChinIn the stable marriagefor a given instance hbe larger matchings.matching that containis not approximable wssing Letterslocate/ipld for nding almost stable-8501, JapanSakyo-ku, Kyoto 606-8501, Japanem that allows incomplete preference lists, all stable matchingsthe same size. However, if we ignore the stability, there canet al. dened the problem of nding a maximum cardinalityimum number of blocking pairs. They proved that this problemsome constant > 1 unless P = NP, even when all preference1K. Hamada et al. / Information Processing Letters 109 (2009) 10361040 1037worun(1beAof(2nastassoleantwnostprtinstantidevore2.ThwfoPrthMwifedwGwmplreanthinsminm(mrtiroThaaa...aaccc...ccanrelowABCDsoanoftoXpafoclLethisCininpaPrm(1k(canAomans preference list is of length at most q. p = q = means that the lengths of preference lists arebounded. Bir et al. [2] showed the following results;) MAX SIZE MIN BP (,)-SMI is NP-hard and cannotapproximated within the ratio of n1 for any constant> 0, unless P = NP; (2) MAX SIZE MIN BP (3,3)-SMI isPX-hard and cannot be approximated within the ratio35573556 1.00028 unless P = NP; (3) MAX SIZE MIN BP,)-SMI is solvable in O (n3) time.In this paper, we improve the hardness of the above (2),mely, we improve the constant 35573556 to n1 for any con-ant > 0. Our reduction uses basically the same ideathe one used in [2] to prove the above (1). In [2],me persons need to have preference lists of unboundedngths for two reasons: One is for garbage collection,d the other is to create a large gap on the costs be-een yes-instances and no-instances. We perform an-trivial modication of the construction and demon-rate that such gadgets can be replaced by persons witheference lists of length at most three.Research on nding almost stable matchings is very ac-ve recently. Abraham et al. [1] consider the problem ofding a matching with the fewer blocking pairs in theable roommates problem, and proved that in most vari-ts the problem is hard, even to approximate. In addi-on to the number of blocking pairs, there are some othernitions of instability, such as the number of agents in-lved in blocking pairs and the number of blocking pairslative to the size of the matching (see [4,5] for example).Main resulteorem 2.1.MAX SIZE MIN BP (3,3)-SMI is not approximableithin n1 where n is the number of men in a given instance,r any > 0, unless P = NP.oof. We demonstrate a polynomial-time reduction frome same problem as [2], EXACT Maximal Matching (EXACT-M) restricted to subdivision graphs of cubic graphs,hich is NP-complete [8]. A graph G is a subdivision graphit is obtained from another graph H by replacing eachge (u, v) of H by two edges (u,w) and (w, v) whereis a new vertex. In this problem, we are given a graphwhich is a subdivision graph of some cubic graph, asell as a positive integer K , and asked if G contains aaximal matching of size exactly K . Hereafter, we sim-y say EXACT-MM to mean EXACT-MM with the abovestrictions.Given an instance (G, K ) of EXACT-MM, we constructinstance I of MAX SIZE MIN BP (3,3)-SMI in such a wayat (i) I has a perfect matching, (ii) if (G, K ) is a yes-stance of EXACT-MM, then I has a perfect matching withall number of blocking pairs, and (iii) if (G, K ) is a no-stance of EXACT-MM, then any perfect matching of I hasany blocking pairs.)-gadget. Before going to the main body of the reduc-on, we rst introduce the(mr)-gadget. This gadget plays ale of garbage collection, just as X and Y in the proof ofeorem 1 of [2].1i : di1 b2i b1i b1i : a1i xi2i : di2 b3i b2i b2i : a2i a1i3i : di3 b4i b3i b3i : a3i a2i...r1i : dir1 bri br1i br1i : ar1i ar2iri : dir bri bri : ari ar1id1j : c2j a j12j : d2j d1j d2j : c3j c2j a j23j : d3j d2j d3j : c4j c3j a j34j : d4j d3j d4j : c5j c4j a j4...m1j : dm1j dm2j dm1j : cmj cm1j a jm1mj : dmj dm1j dmj : cmj a jmFig. 1. Preference lists of C(X, r).Let X be a set of men of size m where X = {x1, . . . , xm},d r (0 < r m) be an integer. The(mr)-gadget (withspect to X and r), denoted C(X, r), consists of the fol-wing 2mr r men (1im Ai) (1 jr C j) and 2mromen (1im Bi) (1 jr D j).i ={a ji : 1 j r},i ={b ji : 1 j r}(1 i m),j ={cij: 2 i m},j ={dij: 1 i m}(1 j r).Each persons preference list is dened in Fig. 1. A per-n ps preference list p : a b c means that p prefers a, b,d c in this order. For each xi X , the unique woman b1iC(X, r) who includes xi in her preference list is referredas C(X, r)[xi].The role of the gadget C(X, r) is to receive any subset X such that |X | = r without creating many blockingirs, as formally stated in the following lemmas. In thellowing lemmas, we assume that each man xi X in-udes the woman C(X, r)[xi] (= b1i ) in his preference 2.2. Let X be a set of men and r be an integer suchat 0 < r |X |. Then, for any X X such that |X | = r, therea matching M for X and C(X, r) such that (i) all members of(X, r) are matched, (ii) all men in X are matched with womenC(X, r) and all men in X \ X are single, and (iii) no personX is included in a blocking pair, and the number of blockingirs for M is at most r.oof. Let X = {xi1 , xi2 , . . . , xir } (1 i1 < i2 < < ir ). We construct the matching M as follows. For each j j r), add the following pairs to M: (aki j ,bk+1i j) for= 1, . . . , j 1; (aki j ,bki j ) for k = j + 1, . . . , r; (aji j,di jj );k+1j ,dkj) for k = 1, . . . , i j 1; (ckj,dkj) for k = i j +1, . . . ,m;d (xi j ,b1i j). (Fig. 2 gives an example for a specic i j .)lso, for each i such that xi X \ X , add (aki ,bki ) for1038 K. Hamada et al. / Information Processing Letters 109 (2009) 10361040kearmLethminPrclangaMofcupaUtespuuggg...ggggg...gguWmuiwbeAldereuiB2Cwarth{ui anFiDeongaI(3eaistimPrprLeMUFig. 2. A part of the matching described in the proof of Lemma 2.2.= 1, . . . , r to M . It is easy to see that (i) and (ii) are satis-d. Also, it is straightforward to check that blocking pairse only (ci jj ,di jj ) (1 j r, i j = 1), and hence there are atost r blocking pairs. mma 2.3. Let X be a set of men and r be an integer suchat 0 < r |X |. Let M be any matching for X and C(X, r) thatatches all members of C(X, r). Then the number of single menX is |X | r.oof. This is obvious because any member in C(X, r) in-udes only persons in C(X, r) and X in the preference list,d there are r more women than men in C(X, r). When X is a set of women, we similarly dene the(mr)-dget by exchanging the roles of men and women.ain part of the reduction. Let I = (G, K ) be an instanceEXACT-MM, where G is a subdivision graph of somebic graph and K is a positive integer. Since G is a bi-rtite graph, we can write it as G = (U ,W , E) such that= {u1, . . . ,un1 } and W = {w1, . . . ,wn2 }, where each ver-x in U (W , respectively) has degree exactly 2 (3, re-ectively). (Hence n1 and n2 are related as 2n1 = 3n2.)1i : z1i wi,pipi z1i : u1i u2i2i : z1i z2i wi,qiqi z2i : u2i g1i,11i,1 : z2i h1pi ,i,pi e1i,1 e1i,1 : g1i,1 g2i,12i,1 : e1i,1 h2pi ,i,pi e2i,1 e2i,1 : g2i,1 g3i,13i,1 : e2i,1 h3pi ,i,pi e3i,1 e3i,1 : g3i,1 g4i,1...C1i,1 : eC2i,1 hC1pi ,i,pi eC1i,1 eC1i,1 : gC1i,1 gCi,1Ci,1 : eC1i,1 hCpi ,i,pi eCi,1 eCi,1 : gCi,1 g1i,21i,2 : eCi,1 h1qi ,i,qi e1i,2 e1i,2 : g1i,2 g2i,22i,2 : e1i,2 h2qi ,i,qi e2i,2 e2i,2 : g2i,2 g3i,23i,2 : e2i,2 h3qi ,i,qi e3i,2 e3i,2 : g3i,2 g4i,2...C1i,2 : eC2i,2 hC1qi ,i,qi eC1i,2 eC1i,2 : gC1i,2 gCi,2Ci,2 : eC1i,2 hCqi ,i,qi eCi,2 eCi,2 : gCi,2 u0i0i : eCi,2 C(U0,n1 K)[u0i]Fig. 3. Preference lists of U(ui).ithout loss of generality, we may assume that K 0, dene= 3/ and C = (n1 + n2)B+1.For each vertex ui U , we construct 2C + 3 men and+ 2 women, whose preference lists are given in Fig. 3,here mens lists are given in the left and womens listse given in the right of the gure. We denote U(ui)e set of these men and women. Dene the set U0 =01, . . . ,u0n1 } (consisting of men, one from each U(ui) (1n1)). We then construct( n1n1K)-gadget C(U0,n1 K ).Similarly, for each w j W , we construct 3C + 3 mend 3C + 4 women, whose preference lists are given ing. 4. We denote W(w j) the set of these men and the set W 0 = {w01, . . . ,w0n2 } (consisting of women,e from each W(w j) (1 j n2)), and construct( n2n2K)-dget C(W 0,n2 K ).The reduction is now completed. The resulting instancecontains the same number n = (2 + 2C + 2n1 2K )n1 ++ 3C + 2n2 2K )n2 + K of men and women. Note thatch persons preference list is of length at most three. Itnot hard to see that the reduction can be performed ine polynomial in the size of I .operties of gadgets. Before proceeding to the correctnessoof, we prove useful lemmas:mma 2.4. For any edge (ui,w j) E, we can form amatchingrestricted to people in U(ui)W(w j) so that (i) all people in(ui)W(w j) are matched, (ii) M contains at most 2 blockingK. Hamada et al. / Information Processing Letters 109 (2009) 10361040 1039vvvfff...fffff...fffff...ffpaI ,aPr(uan(ufo(gkco(v( fs(v(vefoanmclablwSit,vpapaLeofremPronWLeinbyn2foPrUenteMpaan(gCopeinwoftiinungafotoun{wofCmaanyiKscfocoti1j : w1j w2j w1j : v1j u j,r jr j2j : w2j w3j w2j : v1j v2j u j,s js j3j : w3j h1j,1 w3j : v2j v3j u j,t jt j1j,1 : h1j,1 h2j,1 h1j,1 : v3j g1r j , j,r j f1j,12j,1 : h2j,1 h3j,1 h2j,1 : f 1j,1 g2r j , j,r j f2j,13j,1 : h3j,1 h4j,1 h3j,1 : f 2j,1 g3r j , j,r j f3j,1...C1j,1 : hC1j,1 hCj,1 hC1j,1 : f C2j,1 gC1r j , j,r j fC1j,1Cj,1 : hCj,1 h1j,2 hCj,1 : f C1j,1 gCr j , j,r j fCj,11j,2 : h1j,2 h2j,2 h1j,2 : f Cj,1 g1s j , j,s j f1j,22j,2 : h2j,2 h3j,2 h2j,2 : f 1j,2 g2s j , j,s j f2j,23j,2 : h3j,2 h4j,2 h3j,2 : f 2j,2 g3s j , j,s j f3j,2...C1j,2 : hC1j,2 hCj,2 hC1j,2 : f C2j,2 gC1s j , j,s j fC1j,2Cj,2 : hCj,2 h1j,3 hCj,2 : f C1j,2 gCs j , j,s j fCj,21j,3 : h1j,3 h2j,3 h1j,3 : f Cj,2 g1t j , j,t j f1j,32j,3 : h2j,3 h3j,3 h2j,3 : f 1j,3 g2t j , j,t j f2j,33j,3 : h3j,3 h4j,3 h3j,3 : f 2j,3 g3t j , j,t j f3j,3...C1j,3 : hC1j,3 hCj,3 hC1j,3 : f C2j,3 gC1t j , j,t j fC1j,3Cj,3 : hCj,3 w0j hCj,3 : f C1j,3 gCt j , j,t j fCj,3w0j : f Cj,3 C(W 0,n2 K)[w0j]Fig. 4. Preference lists of W(w j).irs, and (iii) for any extension of M to a complete matching ofno person in U(ui) W(w j) will create a blocking pair withperson not in U(ui) W(w j).oof. We construct a matching M as follows. Sincei,w j) E , there are integers k and l such that j,i = kd i, j = l, by the denition of and . We rst addki ,wlj) to M . Next, we consider people in U(ui). Add thellowing pairs to M: (g1i,1, z2i ); (gsi,1, es1i,1 ) for s = 2, . . . ,C ;1i,2, eCi,1); (gsi,2, es1i,2 ) for s = 2, . . . ,C ; and (u0i , eCi,2). If= 1, then add (u2i , z1i ), otherwise, add (u1i , z1i ). Finally, wensider people in W(w j). Add the following pairs to M:3j ,h1j,1); ( fsj,1,hs+1j,1 ) for s = 1, . . . ,C 1; ( f Cj,1,h1j,2);sj,2,hs+1j,2 ) for s = 1, . . . ,C 1; ( f Cj,2,h1j,3); ( f sj,3,hs+1j,3 ) for= 1, . . . ,C 1; and ( f Cj,3,w0j ). If l = 1, add (v1j ,w2j ) and2j ,w3j ); if l = 2, add (v1j ,w1j ) and (v2j ,w3j ); if l = 3, add1j ,w1j ) and (v2j ,w2j ).It is straightforward to verify that condition (i) is satis-d. To see that conditions (ii) and (iii) hold, observe thellowing: In U(ui), all men of the form gsi,t for any t, s,d u0i are matched with their rst choices. Clearly, theseen do not form a blocking pair. Also, women who in-ude only these men in their preference lists cannot formblocking pair. So, only u1i , u2i , z1i , and z2i can form aocking pair. If we check the cases of k = 1 and k = 2,e can verify that at most one blocking pair is possible.milarly, in W(w j), all women of the form hsj,t for anys, and w0j are matched with their rst choices. So, only1j , v2j , v3j , w1j , w2j , and w3j can be a part of a blockingir. We may conclude that there is at most one blockingir by checking cases l = 1,2,3. mma 2.5. In any matching of I that matches all membersU(ui) (W(w j), respectively), all people in U(ui) (W(w j),spectively), except for one man (woman, respectively), areatched among themselves.oof. This is true because any woman in U(ui) includesly men in U(ui) in her preference list. The case for(w j) can be proved similarly. mma 2.6. Suppose that (ui,w j) E. Let M be any match-g of I such that all people in U(ui) and W(w j) are matchedM and both (u0i , C(U0,n1 K )[u0i ]) and (w0j , C(W 0, K )[w0j ]) are in M. Then there are at least C blocking pairsr M (formed by only people in U(ui) W(w j)).oof. Since (u0i , C(U0,n1 K )[u0i ]) M and all people in(ui) are matched in M , by tracing the womens prefer-ce lists, the partners of women in U(ui) are uniquely de-rmined, namely, (gsi,t, esi,t) M for any t, s, and (uti , zti ) for t = 1,2. Similarly, we may uniquely determine theirs within W(w j), namely, ( f sj,t ,hsj,t) M for any t, s,d (vtj,wtj) M for t = 1,2,3.Since (ui,w j) E , there are integers k and l such thatj,i = k and i, j = l by the denition of and . Then, allsi,k,hsj,l) (1 s C ) are blocking pairs for M . rrectness of the reduction. We rst show that I admits arfect matching. As we have assumed that G has a match-g of size K , let it be M . For each edge (ui,w j) M ,e match people in U(ui) and W(w j) as in the proofLemma 2.4. There are exactly n1 K unmatched ver-ces in U . Let U0 ( U0) consist of men correspond-g to these unmatched vertices, i.e. U0 = {u0i : ui U ismatched in M }. We match people in U0 and ( n1n1K)-dget C(U0,n1 K ) as in the proof of Lemma 2.2. Also,r each i such that u0i U0, match every woman in U(ui)her rst choice man. Similarly, there are exactly n2 Kmatched vertices in W . Dene W 0 ( W 0) as W 0 =0j : w j W is unmatched in M }. Again, using the proofLemma 2.2, we match people in W 0 and( n2n2K)-gadget(W 0,n2 K ). Finally, for each j such that w0j W 0,atch every man in W(w j) to his rst choice woman. Bycareful observation, together with Lemmas 2.2 (i) and (ii)d 2.4(i), it can be veried that the above constrictionelds a perfect matching.Now suppose that G has a maximal matching M of size. We construct a perfect matching M of I from M as de-ribed above. We will count the number of blocking pairsr M . By Lemma 2.2(iii), C(U0,n1 K ) and C(W 0,n2 K )ntain at most n1 K and n2 K blocking pairs, respec-vely, and people in these gadgets do not create blocking1040 K. Hamada et al. / Information Processing Letters 109 (2009) 10361040pairs with people outside respective gadgets. Next we lookat gadgets corresponding to vertices. For a pair of verticesui and w j such that (ui,w j) M , there are at most 2blocking pairs formed by people in U(ui) and W(w j) byLemma 2.4(ii). Since |M | = K , there are at most 2K suchblocking pairs. Also, by Lemma 2.4(iii), people in U(ui) andW(w j) do not form blocking pairs with people outsideU(ui) W(w j). Finally, we consider the gadgets corre-sponding to the vertices unmatched in M . Consider thegadget U(ui) where ui is unmatched in M . By the con-struction of M , all women in U(ui) are matched with theirrst choices, and cannot form a blocking pair. Hence onlyth swthmbecawIn(noffo(wseMinthwKthy(erofabthedinwmbytrifperfect matching of I with less than C (= (n1 + n2)B+1)blocking pairs.Hence, the existence of (n1 + n2)B -approximation algo-rithm for MAX SIZE MIN BP (3,3)-SMI implies a polyno-mial-time algorithm for EXACT-MM, which implies P = NP.We will show that (n1 + n2)B n1 . Recall thatn = (2+ 2C + 2n1 2K )n1+ (3+ 3C + 2n2 2K )n2 + K , (1)by which we obtain n 5(n1 + n2)B+2, and hence(n B BB+2BB+2WSispm5BityprAcfoKARe[1[2[3[4[5[6[7[8e possibility is that a man gi, j,i forms a blocking pairith a woman hsj,i, j for some j and s. If this is the case,en (ui,w j) E , but by the maximality of M , w j isatched in M . Then, by the construction of M , hsj,i, j mustmatched with her rst choice and hence (gsi, j,i ,hsj,i, j)nnot be a blocking pair. Similarly, no people in W(w j)here w j is unmatched in M cannot form a blocking pair.summary, the total number of blocking pairs is at most1 K ) + (n2 K ) + 2K = n1 + n2.Conversely, suppose that there is a perfect matching MI that contains less than C blocking pairs. By Lemma 2.5,r each ui U , all people in U(ui), except for one manhich we call a free-man), are matched among them-lves. Hence there are exactly n1 free-men. By Lemma 2.3,matches exactly n1 K men from U0 with womenC(U0,n1 K ). Clearly, all these men are free-men. So,ere are K remaining free-men. We will dene free-omen similarly, and by a similar argument, there areremaining free-women. Since M is a perfect matching,ese men and women are matched together.Dene M as M = {(ui,w j): (x, y) M, x U(ui), W(w j)}. If (x, y) M for some x ( U(ui)) and yW(w j)), then (ui,w j) E by the construction of pref-ence lists of I . Also, it is easy to see that x and y are oneK free-men and free-women, respectively, mentionedove. Hence, M is a matching of G of size K . We showat M is maximal. For, suppose not. Then, there is ange (ui,w j) E both of whose endpoints are unmatchedM . By the construction of M , u0i U(ui) is matchedith the woman C(U0,n1 K )[u0i ] and w0j W(w j) isatched with the man C(W 0,n2 K )[w0j ], in M . But thenLemma 2.6, M contains at least C blocking pairs, a con-adiction. Hence M is maximal, and we can conclude thatG has no maximal matching of size K , then there is no1 + n2) 5 n . (2)e may assume without loss of generality that n1 3.nce each vertex in U and W has degree 2 and 3, re-ectively, 2n1 = 3n2. So, we have n1 + n2 5. Also, K


View more >