Algorithms for graph partitioning on the planted p

Algorith[e-mail]tmentUniversityofWisconsin1210WestDaytonSt.Madison,[e-mail]cienceandEngineeringUniversityofWashingtonSeattle,WA98195October12,2000AbstractTheNP-hardgraphbisectionproblemistopartitionthenodesofanundirectedgraphintotwoequal-sizedgroupssoastominimizethenumberofedgesthatcrossthepartition.Themoregeneralgraphl-partitionproblemistopartitionthenodesofanundirectedgraphintolequal-sizedgroupssoastominimizethetotalnumberofedgesthatcrossbetweengroups.Wepresentasimple,linear-timealgorithmforthegraphl-partitionproblemandanalyzeitonarandom\plantedl-partitionmodel.Inthismodel,thennodesofagrapharepartitionedintolgroups,eachofsizen=l;twonodesinthesamegroupareconnectedbyanedgewithsomeprobabilityp,andtwonodesindierentgroupsareconnectedbyanedgewithsomeprobabilityrp.Weshowthatifprn1=2+forsomeconstant,thenthealgorithmndstheoptimalpartitionwithprobability1exp(n()).1IntroductionThegraphl-partitionproblemistopartitionthennodesofanundirectedgraphintolequal-sizedgroupssoastominimizethecutsize,namelythetotalnumberofedgesthatcrossbetweengroups.Thereisanextensiveliteratureonalgorithmsforthisproblembecauseofitsmanyapplications,whichincludeVLSIcircuitplacement,paralleltaskscheduling,andsparsematrixfactorization.Unfortunatelyeventhespecialcaseofthisproblemwhenl=2,whichisthewell-knowngraphbisectionproblem,isNP-hard[10].Inlightofthis,muchoftheliteratureonalgorithmsforgraphbisection(asformanyotherNP-hardproblems)reportsonaverage-caseperformanceofalgorithms.Suchworkassumesaprobabilitydistributionovertheinputgraphsofagivensize(numberofnodesand/oredges).Whilethebulkofthisworkprovidesonlyempiricaldata,severalpapers,includingthispaper,bound(asafunctionoftheparametersoftherandomgraphmodel)theprobabilitythatCondon’sresearchsupportedbyNSFgrantsHRD-627241andCCR-9257241.yKarp’sresearchsupportedbyNSFgrantDB1-9601046.Currentaddress:DepartmentofElectricalEngineeringandComputerSciences,UniversityofCalifornia,Berkeley,CA94720.1agivenalgorithmndsaminimumbisection.Suchanalysesareusefulinthattheycanprovideinsightonwhenandwhycertainalgorithmicapproachesarelikelytobeeective.ApopularrandomgraphmodelistheG(n;m)modelinwhichagraphisselectedrandomlyanduniformlyfromthesetofallgraphswithnnodesandmedges.AcloselyrelatedmodelistheG(n;p)modelinwhicheachpairofnodesisconnectedbyanedgeindependentlywithprobabilityp.Nopolynomialtimealgorithmisknownthatprovablyndstheminimumbisectionwithhighprobabilityoneitherofthesemodelsforgeneralp.Thelackofsuchananalysismaystemfromthefactthat,ifm=n!1,thenforalmostallgraphswithnnodesandmedgesthecutsizesofthebestandworstbisectionsdierbyonlyaloworderterm(seeBuietal.[3]).Instead,someresearchershaveworkedwithrandomgraphmodelsinwhichthecutsizeofthebestbisectionismuchsmallerthantheaveragecutsize.Theearliestresults,duetoBuietal.[2,3]concernedtheG(n;m;b)model,inwhichagraphischosenrandomlyanduniformlyfromthesetofgraphsthathavennodes,medges,andminimumcutsizeb.Buietal.describeanalgorithm,basedonnetworkowtechniques,thatwithprobability1o(1)ndsanoptimalbisectiononthismodelwiththeadditionalconstraintsthatthegraphisregular,saywithdegreedandb=o(n11=b(d+1)=2c).Sinceeverygraphwithdnedgeshasaveragecutsizedn=2,theminimumbisectionfortheBuietal.graphsisasymptoticallysmallerthantheaveragebisection.DyerandFrieze[6]analyzeanalgorithmfor(notnecessarilyregular)graphswith(n2)edgesandb(1)m=2foraxed0.TheDyer-Friezealgorithmisbasedoncomparisonofvertexdegrees;itndstheminimumbisectioninpolynomialexpectedtime.Boppana[5]presentsagraphbisectionalgorithmbasedoneigenvectormethods.Heshowsthatifmis(nlogn)andb(m5pmnlogn)=2,thenhisalgorithmndstheminimumbisectionwithprobability1O(1=n).Thus,Boppana’sanalysisappliestoalargerclassofgraphsthantheanalysisofeitherBuietal.orDyerandFrieze.However,therunningtimeofBoppana’salgorithmishighsincethealgorithmusestheellipsoidmethodforndingthemaximumofaconcavefunction.JerrumandSorkin[12]analyzedaconstant-temperaturesimulatedannealingalgorithmforgraphbisectiononaslightlydierentrandomgraphmodel.Simulatedannealingisaheuristic,originallyproposedbyKirkpatrick,Gelatt,andVecchi[16],thatcanbeappliedtoawiderangeofcombinatorialproblems.Roughly,inthecaseofthegraphbisectionproblemthisalgorithmattemptstondagoodbisectionfromaninitialbisectionbyrepeatedlyemployingthefollowingprocedure(seeJohnsonetal.[13]).Apairofnodes,oneoneachsideofthecurrentbisection,ischo-sen.Theseareswappedwithsomeprobabilitythatdependsontwoparameters,namelythechangeincutsizethatresultsifthenodesareswappedandatemperatureparameterwhichdecreasesovertime(asthetemperatureparameterisdecreased,sodoestheprobabilityofa\badswap).JerrumandSorkinpointoutthat,althoughthetemperatureparameterisbelievedtoimprovetheeec-tivenessofsimulatedannealingalgorithms,thereisnorigoroustheoreticalanalysisthatsupportsthisbelief.Indeed,JerrumandSorkin’sresultsshowthat,ontheirrandomgraphmodel,withhighprobability,constanttemperaturesi