SIAMJ.COMPUT.Vol.2,No.4,December1973ANns/2ALGORITHMFORMAXIMUMMATCHINGSINBIPARTITEGRAPHS*JOHNE.HOPCROFT"ANDRICHARDM.KARPAbstract.Thepresentpapershowshowtoconstructamaximummatchinginabipartitegraphwithnverticesandmedgesinanumberofcomputationstepsproportionalto(m+n)x/.Keywords,algorithm,algorithmicanalysis,bipartitegraphs,computationalcomplexity,graphs,matching1.Introduction.Supposewearegivenarectangulararrayinwhicheachcellisdesignatedas"occupied"or"unoccupied".Asetofcellsisindependentifnotwoofthecellslieinthesameroworcolumn.Ourobjectistoconstructanindepen-dentsetofoccupiedcellshavingmaximumcardinality.Inoneinterpretation,therowsofthearrayrepresentboys,andthecolumnsrepresentgirls.Celli,jisoccupiedifboyandgirljarecompatible,andwewishtomatchamaximumnumberofcompatiblecouples.Analternatestatementoftheproblemisobtainedbyrepresentingtherowsandcolumnsofthearrayastheverticesofabipartitegraph.Theverticescorrespondingtorowandcolumnjarejoinedbyanedgeifandonlyifcelli,jisoccupied.Wethenseekamaximummatching;i.e.,amaximumnumberofedges,notwoofwhichmeetatacommonvertex.Thisproblemhasawidevarietyofapplications([3],4],[5]).Theseincludethedeterminationofchaindecompositionsinpartiallyorderedsets,ofcosetrepresentativesingroups,ofsystemsofdistinctrepresentatives,andofblock-triangulardecompositionsofsparsematrices.TheproblemalsooccursasasubroutineinthesolutionoftheHitchcocktransportationproblem,andinthedeterminationofwhetheronegiventreeisisomorphictoasubtreeofanother.Inviewofthisvarietyofapplications,thecomputationalcomplexityoftheproblemoffindingamaximummatchinginabipartitegraphisofinterest.Thebestpreviousmethods([1],[3],[4],[5])seemtorequireO(mn)steps,wheremisthenumberofedges,andnthenumberofvertices.ThepresentmethodrequiresonlyO((m+n)x/)steps.Wehopetoextendourresultstothenonbipartitecase(cf.[2]).Withthisinmind,alltheresultsin2arederivedforgeneralgraphs.Thespecializationtothebipartitecaseoccursin3.2.Matchingsantiaugmentingpaths.LetG(V,E)beafiniteundirectedgraph(withoutloops,multipleedges,orisolatedvertices)havingthevertexsetVandtheedgesetE.Anedgeincidentwithverticesvandwiswritten{v,w}.AsetMEisamatchingifnovertexveVisincidentwithmorethanoneedgeinM.Amatchingofmaximumcardinalityiscalledamaximummatching.WemakethefollowingdefinitionsrelativetoamatchingM.AvertexvisfreeifitisincidentwithnoedgeinM.ReceivedbytheeditorsNovember14,1972,andinrevisedformApril23,1973.ThisresearchwassupportedinpartbytheNationalScienceFoundationunderGrantsNSFGJ96,GPo25081andGJ474."DepartmentofComputerScience,CornellUniversity,Ithaca,NewYork,14850.ComputerScienceDepartment,UniversityofCalifornia,Berkeley,California94720.225226JOHNE.HOPCROFTANDRICHARDM.KARPApath(withoutrepeatedvertices)P(v,,v2)(v2,V3),(U2k_1,U2kiscalledanaugmentingpathifitsendpointsvandVzkarebothfree,anditsedgesarealternativelyinEMandinM;i.e.,PCIM{(v2,v3),(v4,vs),(v6,vT),(V2k_2,U2k-1)}"Whennoambiguityispossible,wcletPdenotethesetofedgesinanaugment-ingpathPaswellasthesequenceofedgeswhichisthepathitself.IfSandTaresets,thenSq)TdenotesthesymmetricdifferenceofSandT,andSTdenotesthesetofelementsinSwhicharenotinT.IfSisafiniteset,then]S]denotesthecar-dinalityofS.LEMMA1.IfMisamatchingandPisanaugmentingpathrelativetoM,thenMPisamatching,and[Mq)P]IM]+1.FiguredenotesagraphGwithamatchingMandaugmentingpathPalongwiththematchingM@P.TI-IOREM1.LetMandNbematchings.If]M]r,IN]sands>r,thenMq3Ncontainsatleastsrvertex-disjointaugmentingpathsrelativetoM.Proof.ConsiderthegraphG(V,M@N)withvertexsetVandedgesetMN.SinceMandNarematchings,eachvertexisindicentwithatmostoneedgefromNMandatmostoneedgefromMN;henceeach(connected).componentofGiseither(i)anisolatedvertex,(ii)acycleofevenlength,withedgesalternativelyinMNandinNM,or(iii)apathwhoseedgesarealternativelyinMNandinNM.LetthecomponentsofGbeC1,C2,"’’,Cg,whereC---(V/,Ei).Let6(Ci)]Eif"lN]-]Ef3m].Then6(C)e{-1,0,1},and6(C)1ifandonlyifCisanaugmentingpathrelativetoM.Z((Ci)"-INMI-[MNI-[N[-[M[-sr.HencethereareatleastsrcomponentsCiofGsuchthat6(C)1.Thesecomponentsarevertex-disjoint,andeachisanaugmentingpathrelativetoM.(o)M(b)P(c)M(PFIG.1.GraphGwith(a)matchingM,(b)augmentingpathPand(c)newmatchingMPindarkedgesMAXIMUMMATCHINGSINBIPARTITEGRAPHS227()N(b)M(c)M(NFIG.2.Matchings.N,MandMO)NinagraphG.EdgesofGarenotshown.AnexampleofmatchingsNandMinagraphG(V,E)alongwiththegraph(V,N@M)isgiveninFig.2.COROLLARY1(Berge).MisamaximummatchingifandonlyifthereisnoaugmentingpathrelativetoM.COROLLARY2.LetMbeamatching.Suppose[M[r,andsupposethatthecardinalityofamaximummatchingiss,s>r.ThenthereexistsanaugmentingpathrelativetoMoflength<=2[r/(sr)+1.1Proof.LetNbeamaximummatching.ThenM03Ncontainssrvertex-disjoint(andhenceedge-disjoint)augmentingpathsrelativetoM.AltogetherthesecontainatmostredgesfromM,sooneofthemmustcontainatmostLr/(sr)JedgesfromM,andhenceatmost2[r/(sr)J+edgesaltogether.LetMbeamatching.TheaugmentingpathPiscalledshortestrelativetoMifPisofleastcardinalityamongaugmentingpathsrelativetoM.THEOREM2.LetMbeamatching,PashortestaugmentingpathrelativetoM,andP’anaugmentingpathrelativetoMO)P.ThenIP’I>_-IPI+IPfqP’I.Proof.LetNM09P03P’.ThenNisamatchingandINI--IMI/2,soMNcontainstwovertex-disjointaugmentingpathsrelativetoM;callthemP1andP:.SinceMNP03P’,IP03P’I>=IPxl+IP=I.ButIPxl_->IPIandIPI->_IPI,sincePisashortestaugmentingpath.SoIPP’I>_-IPI/IP21>_-21PI,andalsowehavetheidentityIP@P’I--IPI+IP’I-IPFIP’I.HenceIP’I>-IPIWeenvisagethefollowingschemeofcomputation:startingwithamatchingMo,computeasequenceMo,M1,M2,".’,Mi,".’,wherePiisashortestaugmentingpathrelativetoM,andM+M03P.ThesymbolIx/denotesthegreatestintegerlessthanorequaltox,andIx]denotestheleastintegergreaterthanorequaltox.228JOHNE.HOPCROFTANDRICHARDM.KARPCOROLLARY3.P,P,+11.COROLLARY4.ForallandjsuchthatIP,IPjI,P,andParevertex-disjoint.Proof.Suppose,forcontradiction,thatIP,IPI,<j,andPiandPiarenotvertex-disjoint.Thenthereexistkandsuchthatk<<j,PkandPlarenotvertex-disjoint,andforeachm,k<m<l,P,,isvertex-disjointfromPkandPI.ThenPIisanaugmentingpathrelativetoMk@Pk,SOIPll>=IPI4-IPf-IPll.ButIPllIPl,soIPPllO.ThusPkandPlhavenoedgesincommon.ButifPkandPlhadavertexvincommon,theywouldhaveincommonthatedgeincidentwithvwhichisinMk(Pk.HencePkandP/arevertex-disjoint,andacontradictionisobtained.THEOREM3.Letsbethecardinalityofamaximummatching.ThenumberofdistinctintegersinthesequenceIP01,IPll,...,IPI,islessthanorequalto2[xJ+2.Proof.Letr/sx//-l.ThenIMIrand,byCorollary2,IPI-<_2Ls/J/(sUs/J)/<_2Lw/J+1.Thus,foreach<r,IPilisoneoftheL/J/positiveoddintegerslessthanorequalto2L/3/1.AlsoI/1,"",IPIcontributeatmosts-rdistinctintegers,andthetotalnumberofdis