on the bottleneck shortest path problem

《on the bottleneck shortest path problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

Konrad-Zuse-ZentrumTakustraße7D-14195Berlin-DahlemGermanyfurInformationstechnikBerlin¨VOLKERKAIBELMATTHIASA.F.PEINHARDTOntheBottleneckShortestPathProblemSupportedbytheDFGResearchCenterMATHEONinBerlinZIB-Report06-22(May2006) ONTHEBOTTLENECKSHORTESTPATHPROBLEMVOLKERKAIBELANDMATTHIASA.F.PEINHARDTAbstract.TheBottleneckShortestPathProblemisabasicprobleminnetworkoptimization.Thegoalistodeterminethelimitingcapaci-tyofanypathbetweentwospecifiedverticesofthenetwork.Thisisequivalenttodeterminingtheunsplittablemaximumflowbetweenthetwovertices.Inthisnoteweanalyzethecomplexityoftheproblem,itsrelationtotheShortestPathProblem,andtheimpactoftheunderlyingmachine/computationmodel.1.IntroductionTheBottleneckShortestPathProblem(BSP)isatthecoreofanumberofnetworkoptimizationproblems.Theperformanceofalgorithmsforitissometimescrucialfortherunningtimesofalgorithmsforhigherlevelprob-lemsinwhichitoccursasasubproblem.Twoexamplesarethek–splittableflowproblem[4](wheretherunningtimeoftheunderlyingBSPalgorithmappearsasafactorintheworstcaserunningtimeboundofthepresentedalgorithm)andtheMaxFlowProblem[2,Chapter7].Asoutlinedin[2],theasymptoticalworstcasebehaviouroftheEdmonds–KarpalgorithmcannotbeimprovedbyusingaBSPalgorithmforfindingaugmentingpaths,butitmightstillimprovethepracticalperformance.Westartwithaformaldefinitionoftheproblem.LetG=(V,E)beagraph,eitherdirectedorundirected,withintegraledgeweightsce∈Nforalledgese∈E.Thecapacitybpofapathp(viewedasasetofedges)isgivenbybp:=mine∈pce.(Fortheemptypath,wedefineb∅=∞.)Withrespecttosomefixedstartvertexvertexs∈V,thebottleneckbvofavertexv∈Visbv:=maxpbp,whereprangesoverall(directed)pathsstartinginsandendinginv.Anedgethatdeterminesthecapacityofapathorthebottleneckofavertex(i.e.,anedgeforwhichthecorrespondingminimumisattained)iscalledcriticalforthepathorvertex,respectively.TheBottleneckShortestPathProblem(BSP)istodetermine,foragivengraphG=(V,E),edgeweightsce∈N(e∈E),andastartvertexs∈V,thebottleneckbtofsomespecifiedtargetvertext.Ifwearegiventhebottle-neckbtofsomevertextthenwecanconstructans–t–pathwithcapacitybtinlineartimebyasimplesearchinthegraphobtainedbyremovingalledgesofcapacitylessthanbt.ViewingtheBSPastheproblemtofindamaximalunsplittables–t–flow,itmaynotbetoosurprisingthatonehasadualityrelationviacuts:GivenaBSPinstancewithsources,targett,wehavemaxbp=minmaxce,pqe∈qSupportedbytheDFGResearchCenterMatheoninBerlin.1 2KAIBELANDPEINHARDTwhereprangesoveralls–t–pathsandqoveralls–t–cuts[8],seealso[12,Chap.8].Nevertheless,forourpurposesitwillturnouttobemoreimportantthattheBSPiscloselyrelatedtothe(SingleSource)ShortestPathProblemP(SP)byreplacingthecapacitybpofapathpbythelength`p=e∈pce,and,insteadofmaximizingbp,minimizing`poverallpathsthatconnectsandv.Indeed,aslightlymodifiedDijkstraalgorithmsolvestheBSPintimeO(m+nlogn)(i.e.,asfastastheSPcanbesolvedthisway,see,e.g.,[7,Chap.24.3]).However,lookingabitmorecloselytotheBSPonesoongetstheimpres-sionthatitshouldbesolvablemucheasier(andfaster?)thantheSP.Themostintriguingreasonisthatitistrivialtosolvethedecisionproblem“Isthereans–t–pathofcapacityatleastk?”inlineartime:Justremovealledgeswithweightslessthankandcheckwhetherthereisanys–t–pathleft.ThisisincontrasttotheSP,forwhichitisnotatallclear,whythedecisionproblem“Isthereans–t–pathoflengthatmostk?”shouldbeeasierthanSPitself.WediscussalineartimealgorithmfortheBSPinundirectedgraphsinSection2.InSection3,wedescribeanalgorithmfortheBSPindirectedgraphswithmedgesthatrunsintimeO(mloglogm).TheroleplayedbythemachinemodelsinthesediscussionsistreatedbrieflyinSection4.2.TheBSPinUndirectedGraphsItseemstobefolkloreforalongtimethatalineartimealgorithmfortheBSPinundirectedgraphsexists.Nevertheless,wecouldnotfindanyexplicitreferencetothatintheliterature.Therefore,wedescribesuchanalgorithmbelow(seeAlgorithm1).Tofixsomenotation:ForasubsetSofnodes,wedenotebyδ(S)thesetofalledgeswithoneendpointinSandtheotherendpointnotinS.Fordirectedgraphswefurtherdistinguishthesetsofoutgoingedgesδout(S)andincomingedgesδin(S).Wealsowriteδ(v)forasinglevertexvmeaningδ({v})HerearesomeremarksonAlgorithm1someofwhichwillalsoberelevantlater.•Wealwaysassumethatthegraphsaregivenbymeansofadjacencylists.•Wecanassumethattheedgeshavepairwisedistinctweights;e.g.,bynumberingtheedgesandbreakingtiesinfavorofthelowernumbers.•Itiswellknown(see,e.g.[5,6])thatamedianofmnumbers(anumberkoutofthegivennumberswiththepropertythatbm/2cnumbersarelessthanorequaltokandm−bm/2caregreaterthanorequaltok)canbefoundinlineartime,i.e.,inO(m)steps(see,e.g.,[7,Chap.9.3]).ThiscanbedonebothonapointermachineaswellasonaRAMmachine.•Shrinkingasetofnodescanbedoneinlineartime.Moreprecisely,givenasetS⊆Vofnodesofan(undirected)graphG=(V,E),onecanconstructinlineartimeanothergraphwithnodes(VS)∪{vnew}(wherevnewrepresentstheshrunkensetS),wherev,w∈VSareadjacentifandonlyifvandwareadjacentinG(inthiscase, ONTHEBOTTLENECKSHORTESTPATHPROBLEM3theedgekeepsitsweight),andvnewandw∈VSareadjacentifandonlyifthereissomev∈SsuchthatvandwareadjacentinG(inwhichcasetheedgereceivesthebiggestweightofanyedgeconnectingSandwinG).Algorithm1ABSPalgorithmforundirectedgraphs1:INPUT:anundirectedgraphG=(V,E)withedgeweightsce∈Nforalle∈E,andsourceandtargetverticess,t∈V;w.l.o.g.alledgeweightsaredifferent,andthereisans–t–path.2:InitializeIterationcount←03:whileIterationcount`(e2)impliesce1≥ce2.Forconvenience,westatesuchanalgorithmasAlgorithm2.ItisareformulationofDijkstra’salgorithm.Algorithm2takesasinputtheBSPinstance,ac-ordering`oftheedges,andanassociatedvaluetableT:`(E)→NsuchthatT(`(e))=ce.Asthealgorithmworkswithordernumbersonly,thevaluetableTisusedtomapbackthoseordernumberstotheoriginalcapacities.Algorithm2AlineartimealgorithmforBSPwithsortededgeweights1:INPUT:BSPinstancewithc-ordering`,andvaluetableT2:InitializeemptybucketsB1,...,Bm3:Initializeb(v)←0forallv∈V,thebucketindexofvertexv4:Initializeflagsthatdenotefixedvertexlabels,i.e.,verticesremovedfromthebuckets:f(v)←0,∀v6=s,f(s)←15:forallsv∈δout(s)do6:B`(sv)←B`(sv)∪{v}7:b(v)←`(sv)8:endfor9:SetU←m10:whileU≥0do11:whileBU6=∅do12:Choosev∈BU13:BU←BU{v}14:f(v)←115:ifv=tthen16:STOP:T(b(t))isthebottleneckbetweensandt17:else18:forallvw∈δout(v)withf(w)=0do19:Calculatek←min{b(v),`(vw)}20:ifk>b(w)then21:Bb(w)←Bb(w){w},Bk←Bk∪{w},b(w)←k22:endif23:endfor24:endif25:endwhile26:U←U−127:endwhileAlgorithm3usesAlgorithm2inordertosolvetheBSP(withouthavingac-orderingathands).Itscorrectnessfollowsfromthefactthatthroughoutthealgorithm,theedgesetE0containsanoptimalpath,whosecapacitycan-notexceedU.TherunningtimeofAlgorithm3dependsonsomefunctions(w),wherelines3-12altogetherneedO(mlogs(m))steps.AsthenumberofedgesinE0withweightsatmostUishalvedineachiteration,wehavet=O(m).Thus,ifwesortNkeysinO(NlogN)time,therunningtimes(m)spentinline13isO(mlogm).Line14thusneedsO(m)steps.Bys(m)s(m)settings(m)=logmweobtainanO(mloglogm)algorithmfortheBSPindirectedgraphs. 6KAIBELANDPEINHARDTAlgorithm3ABSPalgorithmfordirectedgraphs1:INPUT:A(possiblydirected)graphG=(V,E)withm=|E|andedgeweightsce∈Nforalle∈E,sourceandtargetverticess,t∈V,anumbers(m);w.l.o.g.alledgeweightsaredifferent,andthereissomes–t–pathinG.2:InitializeIterationcount←0,E0←E,L←mine∈Ece,U=maxe∈Ece3:whileIterationcountM}6:if(V,F)iss–t–connectedthen7:E0←F,L←M8:else9:U←M10:endif11:Iterationcount←Iterationcount+112:endwhile13:Numberthetedgesin{e∈E0:ce≤U}accordingtoincreasingweights:e1,...,et14:SolvetheinstancebyAlgorithm2withthefollowingc-ordering:1ifce≤L`(e)=i+1ife∈E0,e=eit+2ifce>UIfweusethemoresophisticatedpriorityqueueof[16]thatperformssortingNkeysinO(NloglogN)time,weendupwithanO(mlogloglogm)timealgorithmforBSP.Ingeneral,wehave:Theorem2.IfAisasortingalgorithm,whoserunningtimeisboundedbyO(N·s(N)),thenemployingAinAlgorithm3yieldsaBSP-algorithmfordirectedgraphs,whoserunningtimeisboundedbyO(mlogs(m)).ThisholdsoneveryRAMmodelofcomputing.Asprovenin[16,Theorem1.4]sortingNw–bitkeysonaRAMintimeN·s(N)(withadecreasingfunctions(·)),impliesandrequirestheexistenceofamonotonepriorityqueuewithconstanttimesearchfortheminimumkeyandextractionoftheminimumkeyins(N)+O(1)time.Thus,aslongasthefastestalgorithmforSPisaDijkstra–typealgorithmutilizingamonotonepriorityqueue(ands(N)=O(1)isimpossible),theBSPindirectedgraphscanbesolvedfasterthanSPbyAlgorithm3ongraphswithO(n)edges(wherenisthenumberofvertices).NotethatforgraphswithΩ(nlogn)edgesDijkstra’salgorithmalreadyyieldsalineartimemethodforbothSPandBSP.4.DiscussionInthissectionwebrieflycommentonmachinemodelsrelevantforthedifferentresultsconcerningsorting,(monotone)priorityqueues,andSP.Thereareanumberofmachinemodelsconsideredinliterature,reflectingtheevolutionofcomputersaswellasthedesiretoincorporatedifferent ONTHEBOTTLENECKSHORTESTPATHPROBLEM7modelallowedoperationsfurthercharacteristicsPointerMa-comparison,conditionalequivalenttotheTuringchinejumps,indirectaddressingmachineRAMstandardAC0operations:storageisdividedinw–conditionaljumps,directbitword;constantnumberandindirectaddressing,ofregisters;addressesarecomparison,shift,bit–themselveswords(thusw≥wiseBooleanoperations,log(inputsize))addition,subtractionstrongRAMarbitraryAC0operations,manyvariantswithnon–i.e.,anyoperationthatcanstandardAC0operationsetbecomputedinO(1)timeknownonapolynomialsizedcir-cuitTable1.Summaryofcapabilitiesofdifferentcomputingmodelsaspectsofrealworldmachines.AshortsurveyisgiveninTable1.Forfurtherintroduction,seee.g.[1].OurAlgorithm3worksintheRAMmodelofcomputation,inparticularitneedsbucketprocessingormorespecificallydirectaddressing.However,itdoesnotneedanysophisticatedAC0operations,butcanbeimplementedwiththestandardsetoftheseoperations.Thus,dependingonthecapabil-itiesofagivenRAM,wecanchoosethefastestsortingalgorithmforthismodel.Althoughnotpossibleonpointermachines,theuseofbucketsiscomputationallyreasonable,see,e.g.,thesatisfyingcomputationalstudiesofelaboratedcodesforSPbyGoldberg[9].ThelineartimealgorithmforSPbyThorupforundirectedgraphscanbeimplementedwithAC0instructionsonly,althoughnotallofthemareconsideredstandardastheyarenotavailableontodayshardware.Thepriorityqueueof[16]howevereitherusessuperlinearspace,non–standardAC0instructions,orrandomization.Finally,wedonotneedanyrestrictionsonthewordsizewoftheRAMbesidestheusualassumptionthattheinputdatacanberepresentedinsinglewords,i.e.,logm,logU≤w.Thisisduetothefactthatnointermediatedataexceedsthesizeoftheinputdata.References[1]A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,Thedesignandanalysisofcomputeralgorithms.,Addison-WesleySeriesinComputerScienceandInformationProcessing.Reading,Mass.etc.:Addison-WesleyPublishingCompany.X,470p.,1974.[2]R.K.Ahuja,T.L.Magnanti,andJ.B.Orlin,NetworkFlows:Theory,Algo-rithms,andApplications,PrenticeHall,NewJersey,1993.[3]L.AleksandrovandH.Djidjev,Linearalgorithmsforpartitioningembeddedgraphsofboundedgenus,SIAMJournalonDiscreteMathematics9,no.1(1996),pp.129–150.[4]G.Baier,E.Kohler,andM.Skutella¨,Onthek-splittableflowproblem,inAlgorithms-ESA2002.10thannualEuropeansymposium,Rome,Italy,September 8KAIBELANDPEINHARDT17-21,2002.Proceedings,R.M.(ed.)etal.,ed.,no.2461inLect.NotesComput.Sci.,Berlin,2002,Springer,pp.101–113.[5]M.Blum,R.W.Floyd,V.Pratt,R.L.Rivest,andR.E.Tarjan,Lineartimeboundsformediancomputations.,inProc.4thann.ACMSymp.TheoryComput.,Denver1972,1972,pp.119–124.[6]M.Blum,R.W.Floyd,V.Pratt,R.L.Rivest,andR.E.Tarjan,Timeboundsforselection.,J.Comput.Syst.Sci.7(1973),pp.448–461.[7]T.H.Cormen,C.E.Leiserson,R.L.Rivest,andC.Stein,Introductiontoalgorithms.2nded.,Cambridge,MA:MITPress.,2001.[8]D.R.Fulkerson,Flownetworksandcombinatorialoperationsresearch,TheAmer-icanMathematicalMonthly73(1966),pp.115–138.[9]A.V.Goldberg,ShortestPathAlgorithms:EngineeringAspects,inEades,Peter(ed.)etal.,Algorithmsandcomputation.12thinternationalsymposium,ISAAC2001,Christchurch,NewZealand,December19-21,2001.Proceedings.Berlin:Springer.Lect.NotesComput.Sci.2223,502-513,2001.[10]P.Klein,S.Rao,M.Rauch,andS.Subramanian,Fastershortest-pathalgo-rithmsforplanargraphs,inProc.26thACMSymp.onTheoryofComputing,1994,pp.27–37.[11]Plotkin,Rao,andSmith,Shallowexcludedminorsandimprovedgraphdecompo-sitions,inSODA:ACM-SIAMSymposiumonDiscreteAlgorithms(AConferenceonTheoreticalandExperimentalAnalysisofDiscreteAlgorithms),1994.[12]A.Schrijver,CombinatorialOptimization:PolyhedraandEfficiency,no.24inAl-gorithmsandCombinatorics,Springer,2003.[13]W.-K.ShihandW.-L.Hsu,Anewplanaritytest.,Theor.Comput.Sci.223,no.1-2(1999),pp.179–191.[14]M.Thorup,UndirectedSingleSourceShortestPathsinLinearTime,in38thAnnualSymposiumonFoundationsofComputerScience,MiamiBeach,Florida,USA,oct1997,pp.12–21.[15]M.Thorup,Floats,integers,andsinglesourceshortestpaths.,J.Algorithms35,no.2(2000),pp.189–201.[16]M.Thorup,OnRAMpriorityqueues,SIAMJ.Comput.30,no.1(2000),pp.86–109.ZuseInstituteBerlin,Takustr.7,14195Berlin,GermanyE-mailaddress:[kaibel,peinhardt]@zib.de