A fast distributed algorithm for approximating the maximum matching

AndrzejCzygrinow1,Micha󰀅lHa´n´ckowiak2,andEdytaSzyma´nska2

1

2

DepartmentofMathematicsandStatistics

ArizonaStateUniversityTempe,AZ85287-1804,USAandrzej@math.la.asu.edu

FacultyofMathematicsandComputerScience

AdamMickiewiczUniversity

Pozna´n,Polandmhanckow@amu.edu.pledka@amu.edu.pl

Abstract.Wepresentadistributedapproximationalgorithmthatcom-2

β(G),whereputesineverygraphGamatchingMofsizeatleast3β(G)isthesizeofamaximummatchinginG.ThealgorithmrunsinO(log4|V(G)|)roundsinthesynchronous,messagepassingmodelofcomputationandmatchesthebestknownasymptoticcomplexityforcomputingamaximalmatchinginthesameprotocol.Thisimprovestherunningtimeofanalgorithmproposedrecentlybytheauthorsin[2].

1Introduction

Anysetofpairwisedisjointedgesconstitutesamatchingofagivengraph.Fromthealgorithmicpointofviewtwobasicproblemsariseinthecontextofmatchings.Oneistocomputeanymatchingofmaximumcardinality(maximummatching),thesecondoneistoconstructamatchingnotcontainedinanyothermatchingofagivengraph(inclusionmaximalmatching).Thereisrichlitera-tureconcerningsequentialalgorithmsforthemaximummatchingproblem(seeLov´aszandPlummer[5]foranexcellentsurvey).Severalsequentialalgorithmsforgeneralgraphswhicharepolynomialintimeareknownandmanyofthemuseaugmentingpathsasamaintool.Ithasturnedout,however,thateventheverysimplesequentialgreedyalgorithmisnotknowntobeimplementedinparallel.Manyproblemsbecomeevenmoredifficultwhentheparallelnetworkisnotequippedwiththesharedmemorystorage.Theincreasingimportanceoflarge-scalenetworkssuchasInternet,ad-hocandsensornetworkshavemoti-vatedactiveresearchondistributedcomputinginamessagepassingsystems.Adoptingtheexistingsequentialproceduresresultsinaratherveryinefficientschemeandanewalgorithmicapproachisneeded.

WeconsiderthedistributedmodelofcomputationintroducedbyLinialin[6].Inthismodelanetworkisrepresentedbyanundirectedgraphwhereeach

󰀁

ResearchsupportedbyKBNgrantno.7T11C03220

vertexstandsforaprocessorandeachedgecorrespondstoaconnectionbetweentwoprocessorsinthenetwork.EachprocessorhasauniqueIDandknowsthenumberofverticesinthegraphbutnottheglobaltopologyofthenetwork.Weassumefullsynchronizationofthenetwork:computationisperformedinsteps.Inasinglestep,eachprocessorcansendamessagetoallofitsneighbors,col-lectmessagesfromitsneighbors,andperformsomelocalcomputations.NotethattheabovemodeliscompletelydifferentfromtheparallelPRAMmodelwhereeachcomputationalunitcancommunicatewithallotherunitsateachstepofthecomputations.Asaresultmanyproblemsthatadmitefficientalgo-rithmsinthePRAMmodelarestillopeninthedistributedmodel.Aneminentexample,whichisageneralizationoftheproblemstudiedinthiswork,istheMaximalIndependentSet(MIS)Problem.EfficientNCalgorithmsforMISarewell-known([7])butthequestionifthereisanefficientdistributedalgorithmfortheproblemisoneofthemainopenproblemsinthearea([6]).However,anefficientdistributedalgorithmfortherelatedMaximalMatching(MM)ProblemisknownduetoHa´n´ckowiak,Karo´nski,andPanconesi.In[4]thethreeauthorsprovedthefollowingtheorem.

Theorem1([4]).ThereisadistributedprocedureMatchwhichinO(log4n)manycommunicationroundsinthesynchronous,distributedmodelofcomputa-tion,computesamaximalmatchingMinanygraphGonnvertices.

TheprocedureMatchisastartingpointforfurtherresearchin[2]andinthispaper.In[2],buildingonideasfrom[4],theauthorsdesignedanalgorithmwhichfindsamaximalmatchingofsizewhichisrelativelyclosetothemaximum:Theorem2([2]).ThereisadistributedalgorithmwhichinO(log6n)stepsfindsamatchingMinanygraphGonnvertices,suchthat

|M|≥

2

β(G)3

whereβ(G)denotesthesizeofthelargestmatchinginG.

Inthispaper,weproposeasubstantialmodificationofthealgorithmfromTheo-rem2whichrunsinO(log4n)stepsandthereforehasthesametimecomplexityasthealgorithmMatchinTheorem1.Thefollowingtheoremisproved:Theorem3.ThereisadistributedprocedureMatchingwhichinO(log4n)stepsfindsinanygraphG(V,E)withn=|V(G)|verticesamatchingM,suchthat

2

|M|≥β(G).

3Althoughtheapproximationratioofourresultmaynotbeveryappealing,itshouldberememberedthattheproblemofcomputinganoptimalsolutioninageneralgraphisevennotknowntobeinNC.Andyettheapproximationalgorithmgivenby[3]isinherentlydesignedfortheEREWPRAM.

Interestingly,theresultispurelydeterministicandtogetherwith[4]standsamongfewexamplesofdistributedcomputing,wherepolylogarithmictimecom-plexityisachievedwithouttheuseofrandombits.TheO(log6n)complexityofthealgorithmfromTheorem2comesfromsequentialiterationsoverO(log2n)blocks(definedinthenextsection).Itisthispartofthealgorithmwhichweimprove.ThemodificationthatwepresentallowsustoperformcomputationsinparallelandasaresultwedroptheO(log2n)factorinthetimecomplexityaltogether.

Followingthestrategyfrom[2],wecomputeamaximalmatchingMandthenamaximalsetofvertex-disjointpathsoflengththreethataugmentM.AfteraugmentingthematchingMalongthesepathsweobtainanewmatchingM󰀂

2

suchthat|M󰀂|≥3β(G).TofindamaximalmatchingweinvoketheprocedureMatchfromTheorem1andtocomputeamaximalsetofdisjointpathswedesignanewprocedure,whichisthemaincontributionofthispaper.

Inthenextsection,wepresentdefinitionsandnotationwhicharenecessarytodevelopthealgorithmtogetherwithsomepreliminarylemmas.Thelastsec-tioncontainsthedescriptionofthealgorithmandasketchoftheproofofitscorrectness.Forcompleteproofsthereaderisreferredtothefullversionofthispaper.

2Definitions,NotationandPreliminaryLemmas

Inthissectionwefixsomenotation,introduceterminology,andstateafewusefullemmas.Asouralgorithmcreatesanauxiliarymultigraph,wedefinemostofthetermsinthemultigraphsetting.

LetMbeamatchingina(multi)graphG=(V,E).WesaythatavertexvisM-saturatedifvisanendpointofsomeedgefromM.Anedgee={u,v}isM-saturatedifeitheruorvisM-saturated.ApathPisM-alternatingifitcontainsalternatelyedgesfromMandfromE\\M.ApathPoflength2k+1,k≥0,augmentsMifPisM-alternatingandnoendofPisM-saturated.AspecialroleinthepaperwillbeplayedbypathsoflengththreeaugmentingM.Apathiscalledan(M,3)-pathifitaugmentsMandhaslengththree.Asetofpathsiscalledindependentifeverytwopathsfromthesetarevertex-disjoint.

Justlikein[2],ouralgorithmisbasedonthefollowingfactsthatarestandardingraphtheory.Claim4

(a)LetMbeanarbitrarymatchinginG.Iftherearenopathsoflengthatmost

threeaugmentingM,then

2

|M|≥β(G).

3

(b)LetMbeamaximalmatchinginagraphGandletPbeamaximalin-󰀂

dependent󰀁setofpathsoflengththreeaugmentingM.Further,letM=M÷(P∈PE(P))bethematchingobtainedbyaugmentingMalongthepathsfromP.ThentherearenopathsoflengthatmostthreeaugmentingM󰀂inG.

Consequently,parts(a)and(b)ofClaim4togetherassure,thatthematchingMsatisfies

2

|M󰀂|≥β(G).

3

Intheprocessofconstructingthematchingwewillusethenotionofasubstantialmatching.

󰀂

Definition1.LetMbeamatchinginamultigraphG=(V,E)andγ>0.AmatchingMisγ-substantialinGifthenumberofM-saturatededgesofGisatleastγ|E|.

Usinganalgorithmfrom[4](withminorchanges),wecanfindasubstantialmatchinginabipartitemultigraph.

Lemma1.ForallconstantsC>0and0<γ<1thereexistsadistributedalgorithmthatfindsinO(log3n)stepsaγ-substantialmatchinginabipartitemultigraphG=(L,R,F),where|F|≤nCand|L|+|R|=n.

Similarly,wewillalsousethenotionofasubstantialsetofpaths.LetP3(M)denotethesetofall(M,3)-pathsinagraphG=(V,E).

Definition2.LetMbeamatchinginGandγ>0.AsetPof(M,3)-pathsiscalledγ-path-substantialinGifthenumberofpathsfromP3(M)thathaveacommonvertexwithsomepathinPisatleastγ|P3(M)|.

Nowwewillintroducemoretechnicalterminology.Givenabipartitemulti-graphH=(L,R,E)wepartitionitsleft-handsideLintosetsLi={u∈L:Dii

21.|A󰀂|≥α|A|.

2.Foreveryvertexa∈A󰀂,degS(a)=1.3.Foreveryvertexb∈B,degS(b)Inotherwords,aspannerisacollectionofstarssuchthatthedegreesofthecentersofthestarsareappropriatelyboundedintermsoftheirdegreesinH.Notethatspannersplayedanimportantroleindesigningthealgorithmformaximalmatchingin[4].Althoughtheproceduresin[4]areformulatedforsimplegraphstheycanbeadoptedtomultigraphswithonlyminorchanges.Inparticular,wehavethefollowingfact.

Lemma2([4]).ForeveryconstantCandinputparameterDthereexistaconstantK=K(C)andadistributedalgorithmthatfindsinO(log3n)stepsa1(2,K)-spannerinamultigraphH=(A,B,E)thatisaD-blockwith|E|≤nCandn=|A|+|B|.

Specifically,inourcaseC=4andK<100.

Inordertomotivatethefollowingdefinitions,wespendsometimeonex-plainingthemainideaofouralgorithm.

Theapproachusedtofindasetofaugmentingpathsisbasedonthefollowingstrategy.FirstwefindamaximalmatchingMusingtheprocedureMatchgiveninTheorem1.Thenthemaximalindependentsetof(M,3)-pathsisgraduallyconstructedinrounds.Ineachroundasubstantialsetof(M,3)-pathsisfound.Itturnsoutthatwecanfindasubstantialsetof(M,3)-pathsinaspeciallayeredgraph.Forthatreason,fromtheinputgraph,weobtainavirtualauxiliarygraphwhichisoftheform.Finally,oncethepathsarefoundinthelayeredgraph,wetranslatethembacktotheoriginalgraph.

Thelayeredgraphwillbeasimplegraphwhichhasfourlayersofverticesandwewillrefertoitasa4L-graph.Apreciseconstructionofa4L-graphisgiveninprocedureReduceplacedinthenextsectionandherewejustintroduceitsstructuralfeatures.Every4L-graphH=H(G,M),withrespecttoGandamaximalmatchingM,hasthevertexsetV(H)partitionedintofournonemptysetsX1,X2,X3,X4sothatH[X2,X3]=MandeveryvertexfromX1isadjacentonlytoverticesfromX2andeveryvertexfromX4isadjacentonlytoverticesfromX3.Inotherwords,Hconsistsof3bipartitegraphs.TheedgesofH[X1,X2]andH[X3,X4]arepotentialingredientsofthe(M,3)-pathsextendingM.Thedesiredstructureofa4L-graphisobtainedbyfirstremovingfromE(G)alledgeswhichviolatetheaboveproperties.WewilldistinguishintheinputgraphGthreetypesofedgeswithrespecttoM:

(a)edgesthatareinM,

(b)edgesthathaveexactlyoneendpointinM(theseedgesmayformtriangles

basedonanedgefromM),

(c)edgesthatarenotinMbuthavebothendpointsinM.

Notethatedgesfrom(c)donotbelongtoany(M,3)-pathofGandthereforewecandeletethem.Next,thetrianglesbuiltofedgesoftype(b)arecarefullydestroyed(seeprocedureReduce).Finally,someverticesfromV(G)\\V(M)arereplicatedtohavetheircounterpartsinX4andX1,respectively.

LetH=(X1,X2,X3,X4,E)bea4L-graph.NowweintroduceanauxiliarymultigraphMul(H)=(X1,X2,X3,X4,F)definedasfollows.

Definition4.LetH=(X1,X2,X3,X4,E)bea4L-graphandforeverye∈H[X1,X2]∪H[X3,X4],letwedenotethenumberof(M,3)-pathsinHcontaininge.ThemultigraphMul(H)=(X1,X2,X3,X4,F)isagraphobtainedfromHbyputtingwecopiesofeinFforeveryedgee∈H[X1,X2]∪H[X3,X4],andonecopyofeforeveryedgee∈H[X2,X3]inF.

ThemainpropertyofMul(H)isthatedgesinMul(H)[X1,X2]andsimilarly,inMul(H)[X3,X4]correspondto(M,3)−pathsinH.InthecourseofourproofwewillmakeuseofitbyfindingasubstantialmatchinginMul(H)[X1,X2]anddeducingasubstantialpropertyforasetof(M,3)−pathsbuiltonthematching.DirectlyfromDefinition4wecanderivethefollowingfact.

Fact5Foreverye={a,a󰀂}∈H[X2,X3],degMul(H)(a)=degMul(H)(a󰀂)whichisequaltothenumberof(M,3)-pathscontaininge.Moreover,thereisaone-to-onecorrespondencebetweentheedgesinMul(H)[X1,X2]andthe(M,3)-pathsinH.

Tothisend,inMul(H),wedefinea4L-D-block.Theactualprocessofcon-structingthesetof(M,3)−pathswillbeperformedinblocksthatwillpartitionthesetsX2andX3.

Definition5.LetRbethesetofalledgese={a,a󰀂}∈Mul(H)[X2,X3]thatsatisfy

D

andletX2=(e∈Re)∩X2,X3=(e∈Re)∩X3.A4L-sub-multigraphBD(H)=

󰀂󰀂

(X1,X2,X3,X4,F󰀂)ofMul(H)=(X1,X2,X3,X4,F)whichcontainsalledgesincidenttoedgesfromRiscalleda4L-D-block.

Itisworthnoticinghere,thatconsideringD=D(i)=2ifori=0,1,...,logn,4L-blocksBD(i)areedgedisjointandpartitionthesetsX2andX3.Whatismore,everysubgraphBD(i)(H)[X3,X4]isaD(i)−block.

3Algorithm

Inthissectionwepresentthemainalgorithm.Ineachiterationitconstructsasubstantialsetof(M,3)-pathsandaddsthemtotheglobalsetofindependent(M,3)-paths.Thenthepathsareremovedfromthegraphtogetherwithalledgesincidenttothem.ItstopswhennosuchpathsareleftinthegraphandoutputsanewmatchingM∗.Belowwepresentanoutlineofthealgorithmtogivesomeintuitionbehindourapproach.

ProcedureMatching

Input:GraphGOutput:MatchingM∗

1.FindamaximalmatchingMinG.2.Forj:=1toO(logn)do

¯=G¯(G,M)=(X1,X2,X3,X4,E)fromGand(a)Constructa4L−graphG

M.

󰀃=Mul(G¯)=(X1,X2,X3,X4,F)withmulti-(b)ConstructamultigraphG

¯[X1,X2]andG¯[X3,X4].pleedgesinG

󰀃ofdisjoint(M,3)-pathsinG󰀃using(c)Findaξ−path-substantialsetP

spannersinblocksinparallel.

󰀃foundinG󰀃toPinG.(d)TranslateP

(e)Accumulatethe(M,3)-pathsfromP.

(f)UpdateG(removefromGthepathsinPwithalledgesincidentto

them).

3.UpdateM∗byaugmentingMalongthepathsfromP.

Thealgorithmconsistsofaprocedurethatcomputesasubstantialmatching,andtwoproceduresfrom[2].Firstwedescribeanewprocedurewhichcomputesasubstantialsetof(M,3)-pathsinagiven4L-graph.Thenwerecalltwoproce-duresfrom[2];thefirstonereducesagraphG=(V,E)andamaximalmatching

¯=(X1,X2,X3,X4,E),thesecondonetranslatesaαMinGtoa4L-graphG󰀃-󰀃ofindependent(M,3)−pathsinG󰀃toα-substantialsetPofsubstantialsetP

independent(M,3)−pathsinG.3.1

Algorithmina4L-graph

Inthissection,wepresentthemainpartofouralgorithm,ProcedurePaths-In4LGraph.Thisprocedurefindsaξ-path-substantialsetPofdisjoint(M,3)-pathsinalayeredgraph.Wearebuildingthepathsintwophases.Inthefirst

¯[X3,X4]whichwillaugmentthematch-phasewechoosecandidatesforedgesinG

ingM.ThisisperformedbyfirstconstructingastarforestwithallstarshavingcentersinX4.Afterthesecondphaseatmostoneedgefromeverystarisaddedtothesetof(M,3)-paths.ThereforewemovealongthestarraystothesetX2andintroduceanauxiliary,bipartitegraphwithverticescorrespondingtothestarswejustcreated,ononesideandX1ontheother.Inthesecondphasewemoveourattentiontothisgraphandfindasubstantialmatchinginit.After

󰀃[X3,X4]weobtainthesetPofextendinguniquelythematchingtothegraphG

disjoint(M,3)−paths.

PhaseA:Steps1-5constructastarforestS󰀂inH[X3,X4].PhaseB:Steps6-8constructthesetPusingS󰀂.

NotethatPhaseBisanalogoustothemainalgorithmforthe4L-graphin[2].However,sincetheblocksinPathsIn4LGrapharedefinedinanewwaycom-paredwith[2],theanalysisisdifferent.ThemainprobleminPathsIn4LGraphistodesignthestarforestS󰀂sothatthestarscanbegluedtogetherandusedassuper-verticesinPhaseB.PropertiesofS󰀂whichweneedtoprovethatthealgorithmisindeedcorrectarequitedelicate,ononehandwemustdeletesomeedgesofaunionofspannersStomaketheanalysiswork,ontheotherweneedtokeepmostofthemtoretainthesubstantialproperty.Inparticular,ifastarhasexactlyonevertexinablockthenitmusthavenoverticesinanyotherblock.Thisistakencareofinsteps(4)and(5)oftheproceduregivenbelow.

ProcedurePathsIn4LGraph

¯=(X1,X2,X3,X4,E),whereG¯[X2,X3]=M.Input:4L-graphG

¯forOutput:AsetPofdisjoint(M,3)-pathswhichisξ-path-substantialinG

someconstantξ>0.

󰀃:=Mul(G¯)asinDefinition4.1.Constructthe4L-multigraphG

2.Fori=0to4logndoD(i):=2i

󰀃)=(X1,X2(i),X3(i),X4,Ei),Bi:=BD(i)(G

whereXj(i)isasubsetofXjcorrespondingtotheblockBi,forj=1,2.3.Inparallel,foreveryi:LetK=K(4)beaconstantinLemma2.Finda(12,K)-spannerSifromX3(i)toX4inBi[X3(i),X4](usingtheprocedurefrom[4]).

4log󰀁n

Sibeastarforest.4.LetS=

(a)ForanystarQ∈SletQi:=Q∩Si.

(b)ForstarQinSletIQ:={i:|Qi|=1}(i.e.Qiisanedge)andlet

JQ={i:|Qi|>1}.

󰀃[X3,X4]thatareincidenttovertices(c)LetiQbethenumberofedgesofG

󰀁󰀃[X3,X4]thatarefromi∈IQV(Qi)∩X3.LetjQbetheofedgesofG

󰀁

incidenttoverticesfromi∈JQV(Qi)∩X3.

iQ=jQ=

󰀄

v∈V(Qi)∩X3

i∈IQ

i=0

dG󰀃[X

3,X4]

(v)(v)

󰀄

v∈V(Qi)∩X3

i∈JQ

dG󰀃[X

3,X4]

5.Inparallel,foreverystarQ∈S:󰀁

(a)IfiQ>jQthendeletefromQalltheedgesthatbelongtoi∈JQQi.In

addition,selectk∈IQsuchthatk=maxIQanddeletefromQallstarsQiforwhichi=k.AsaresultQistheedgeQk.󰀁

(b)IfiQ≤jQdeletefromQalltheedgesthatbelongtoi∈IQQi.LetS󰀂denotethestarforestaftertheseoperations.

󰀂=(X1,X󰀂,E󰀂)withX󰀂=6.Constructthefollowingauxiliarymulti-graphG22

󰀂󰀂󰀂󰀂󰀃{NX2(Q):Q∈S}andthesetofedgesE={{u,v}∈G:u∈X1andv∈

NX2(Q󰀂)forsomeQ󰀂∈S󰀂}.

󰀂.7.Finda1/2-substantialmatchingM󰀂inG

8.Extend(inauniqueway)everyedgeofM󰀂toapathPoflengththreeinthegraphusinganedgeofmatchingMandanedgeofastarinS󰀂.PisthesetofallpathsPobtainedfromM󰀂.Wewillneedsomemorenotationinthenexttwolemmas.RecallthatSisasetofstarswithcentersinX4.LetF4bethesetofverticesofstarsfromSwhichareinX4,F3thesetofverticesofstarsinSwhichareinX3.Inaddition

󰀂󰀂󰀂

,andF2.,F3letF2:=N(F3)∩X2.Similarly,byconsideringS󰀂,wedefineF4

Thefollowinglemmaestimatesthenumberofedgesthatwemaylosewhileconcentratingonthestarsonly.

1󰀂

Lemma3.1.eG

󰀃(F3,X4)≥32eG󰀃(X3,X4)1󰀂

2.eG

󰀃(X1,X2).󰀃(X1,F2)≥32eG

Proof(Sketch).ByFact5,theproofofbothpartsisthesame,anditfollows

fromapropertyofthespannersSi(seePart1.ofDefinition3).

1

Lemma4.LetK=K(4)begiveninLemma2andletξ=256K.Thesetof

¯pathsPfoundbyPathsIn4LGraphisξ-path-substantialinG.Thealgorithm

¯))steps.PathsIn4LGraphrunsinO(log3V(G

Proof(Sketch).Firstnotethatthetimecomplexitycomesfromfindingspanners

inalltheblocks(inparallel)instep(3)andbyLemma2isO(log3n).LetPbethesetof(M,3)−pathsfoundbytheprocedurePathsIn4LGraph.InviewofFact5,toprovethatPisξ-path-substantial,weneedtoshowthateitherξ-󰀃[X1,X2]isincidenttoedgesofpathsfromPorξ-fractionfractionofedgesinG

󰀃[X3,X4]isincidenttoedgesofpathsfromP.ForthatweconsiderofedgesinG

󰀂foundinStep(7)andthesetWofverticesinX2thatareamatchingM󰀂inG

inM󰀂-saturatedsuperverticesandarenotsaturatedbyM󰀂themselves.ThenweconsidertwocasesbasedonthenumberofedgesincidenttoWwithrespectto

1󰀂

eG

󰀃(X1,X2).IfitrelativelysmallthenthefactthatMis2-substantialcombined

1

withLemma3impliesthatξ=128.Thesecondcaseisabitmorecomplicated.WemoveourattentiontothelayersX3andX4.IncorporatingthepropertiesofthestarforestS󰀂andtheupperboundonthedegreeofspanners,weshow

1

thatatleast256K-fractionofedgesinEG

󰀃(X3,X4)isincidenttocentersofstars

1

saturatedbypathsfromP.ThetwocasesyieldtheLemmawithξ=256K.3.2

Reduction,Translation,andModification

Asindicatedinprevioussectionsourmainalgorithmcanbesummarizedasfollows.FirstcomputeamaximalmatchingM,nextiterateO(logn)timesthe

¯,followingsteps:(1)ReducegraphGandmatchingMtoalayeredgraphG

¯ofdisjoint(M,3)-pathsinG¯usingPathsIn4LGraph,(3)(2)FindasetP

¯topathsPinGmaintainingthesubstantialproperty,TranslatepathsfromP

¯withrespectP.Inthissection,wepresentprocedures:(4)ModifyGandG

¯;1.ReducewhichreducesGandMtoa4L-graphG

¯toasetofpathsPinG;2.TranslatewhichtranslatesP

¯withrespecttoP.3.ModifywhichmodifiesG

ProceduresReduceandModifyaresimilartoproceduresin[2],Translate

differsfromthecorrespondingprocedurein[2]onlybysmalldetails.

ProcedureReduce

Input:GraphGandamaximalmatchingMinG.

¯Output:4L-graphG.

1.Fore∈E(G)(inparallel)checkifeiscontainedinatleastone(M,3)-path.

Ifitisnotthendeletee.Inparticular,alledgesfromE(G)\\MwhichhavebothendpointsinMaredeleted.

2.Foreveryedgem={m1,m2}∈M,withID(m1)Foreveryvertext∈Tm,1deletetheedge{t,m2}fromthegraph,foreveryvertext∈Tm,2delete{t,m1}.Asaresult,the”new”graphG󰀂doesnothavetrianglesbasedonedgesfromM.FromnowonwewilloperateonG󰀂.3.Foreveryedgem={m1,m2}∈M,withID(m1)4.Foreveryvertexv∈G\\V(M),splitvintototwosiblingsv−andv+,wherev−inheritsallthearcsthatstartinv,v+inheritsarcsthatendinv.Finally,ignoretheorientationontheedges.Asaresultweobtaina4L-graph¯=(V−,V1(M),V2(M),V+),whereV−={v−,v∈V(G)\\V(M)},V+=G

{v+,v∈V(G)\\V(M)},andV1(M),V2(M)arecorrespondingendpointsofMthatisifm={m1,m2}∈MandID(m1)onedgesfromMandthenusingorientationtosplitM-unsaturatedverticesintoV−andV+(see[2]fordetails).TherearetwomainpropertiesofReducethatareusefulforouranalysis.

¯,m󰀂thenumberofLemma5.Letm¯3denotethenumberof(M,3)-pathsinG3

󰀂

(M,3)-pathsinG,andm3denotethenumberof(M,3)-pathsinG.Then1.m󰀂¯3,3=m2.m3/4≤m󰀂3.

−+¯thenv1m1m2v2is(M,3)-pathinFact6Ifv1m1m2v2isan(M,3)-pathinGG.

OurnextproceduremodifiesGwithrespecttothesetof(M,3)-pathsP.TheproceduredeletesalledgeswhichareincidenttopathsfromP.Asaresult,itispossiblethatsomeedgespresentinthemodifiedgraphG󰀂willnotbelongtoany(M,3)-pathofG󰀂.Theseedgesaresubsequentlydeletedinstep(1)ofReduce.

ProcedureModify

Input:GraphGandasetPof(M,3)-pathsinG.Output:ModifiedG󰀂.

󰀁

1.Foranyedgee∈P∈P

󰀁E(P)inparallel:deleteedgesthatareincidenttoe

2.DeletealledgesfromP∈PE(P)

Finally,inthelastprocedureofthissection,weshowhowtotranslateaset

¯inG¯toasetofpathsPinG.RecallthatG󰀂denotesthesubgraphofpathsP

ofGobtainedbydestroyingtrianglesthatcontainedgesfromM,instep(2)ofReduce.

ProcedureTranslate

¯ofindependent(M,3)-pathsinG¯.Input:SetP

Output:SetPofindependent(M,3)-pathsinG.

1.Identifyverticesv−andv+thatcorrespondtoonevertexv∈V(G).Asa

¯cyclesandpathsingraphG.ThesepathsandcyclesresultweobtainfromP

havelengthsoftheform3iwherei>1andarebuiltupfrom(M,3)-paths.2.Treat(M,3)-pathsasedgesbetweenendpointsofthesepaths.Nowtheprob-lemofselectingasetofindependent(M,3)-pathsinGisreducedtotheoneoffindingasubstantialsetofindependentedges.Invokeanalgorithmfrom[4]toobtainsetPofindependent(inG)(M,3)-paths.ThesetPhasthefollowingproperty:Ifthenumberof(M,3)-pathsinG󰀂whichareincident󰀁󰀂toedgesofP∈Pleastαm󰀂¯E(P)isat3thenatleastαm3/4,(M,3)-pathsin󰀁

G󰀂areincidenttoedgesofP∈PE(P).NotethattheresultingsetPisasetof(M,3)-pathswhichareindependentinG.Inadditionthesetispath-substantialwithaconstantspecifiedinthenextlemma.

¯isξ-path-substantialinG¯thenthesetofpathsLemma6.IfasetofpathsP

PobtainedbyprocedureTranslateisξ/16-path-substantialinG.Proof.TheprooffollowsfromLemma5andStep(2)ofTranslate.3.3

MainProcedure

Nowwecansummarizethediscussioninourmainalgorithm.WedenotebyA÷BthesymmetricdifferencebetweenAandB.

ProcedureMatching

Input:GraphG.

2

Output:MatchingM∗suchthat|M∗|≥3β(G).

1.FindamaximalmatchingMusingtheprocedureMatchfrom[4].2.LetPI:=∅andM∗:=M.3.IterateO(logn)times:

¯.(a)InvokeReducetoobtaina4L-graphG¯.(b)InvokePathsIn4LGraphtoobtainP

(c)UseTranslatetoobtainP.

¯withrespecttoP.(d)UseModifytomodifyG

(e)PI:=PI∪P.

󰀁

4.M∗:=M∗÷(P∈PIE(P)).

Proof(ofTheorem3).Firstweestablishthetimecomplexity.WeuseO(log4n)roundsinthefirststep,tofindMusingthealgorithmfrom[4].Ineachiteration,themaintimecomplexitycomesfromPathsIn4LGraphwhich,byLemma4

¯))=O(log3n).SincewehaveO(logn)iterations,thenumberofisO(log3V(G

stepsisO(log4n).

¯foundineachiterationis1-path-ByLemma4,thesetofpathsP256K1¯substantialinG.Therefore,byLemma6,Pis4096K-path-substantialinG

andsoinstep(3d)aconstantfractionof(M,3)-pathswillbedeletedfromG.Sincethenumberof(M,3)-pathsinGisO(n4),therewillbeno(M,3)-pathsinGafterO(logn)iterations.Consequently,afterstep(3),PIisamaximalsetof(M,3)-paths.Thus,afterexchangingedgesinstep(4),weobtainmatchingM∗suchthatthereisno(M∗,3)-pathinG.Therefore,byClaim4,|M∗|≥23β(G).FinalRemarks.Anefficientrandomizedalgorithmforapproximatingthemaxi-mummatchingcanbeobtainedbyinvokingarandomizedMISprocedure([7])inanauxiliarygraphwherethevertexsetconsistsofaugmentingpathsandtwoverticesareconnectedifthecorrespondingpathsshareavertexintheoriginalgraph.

Theaugmentingpathstechniquecanonlybeappliedtoanunweightedver-sionoftheproblem;toapproximateamaximumweightedmatchingacompletelydifferentapproachmustbetaken.

References

1.Awerbuch,B.,Goldberg,A.V.,Luby,M.,Plotkin,S.:Networkdecomposi-tionandlocalityindistributedcomputing.Proc.ofthe30thSymposiumonFoundationsofComputerScience(FOCS19)3–3692.Czygrinow,A.,Ha´n´ckowiak,M.,Szyma´nska,E.:Distributedalgorithmforapproximatingthemaximummatching.DiscreteAppliedMath.publishedonline(March19,2004)

3.Fischer,T.,Goldberg,A.V.,Haglin,D.J.,Plotkin,S.:Approximatingmatchingsinparallel.InformationProcessingLetters46(1993)115–1184.Ha´n´ckowiak,M.,Karo´nski,M.,Panconesi,A.:Onthedistributedcomplexityofcomputingmaximalmatchings.SIAMJ.DiscreteMath.Vol.15,No.1,(2001)41–575.Lov´asz,L.,Plummer,M.:MatchingTheory.Elsevier,AmsterdamandNewYork(1986)

6.Linial,N.:Localityindistributedgraphalgorithms.SIAMJournalonCom-puting21(1)(1992)193–201

7.Luby,M.:ASimpleParallelAlgorithmfortheMaximalIndependentSetProblem.SIAMJ.onComputing15(4)(1986)254–278.