maximum-flow-acceleration-by-traversing-tree-based-two-boundary-graph-contraction原版完整文件

Contentslistsavailableat

ScienceDirect

ExpertSystemsWithApplications

journalhomepage:

/locate/eswa

ExpertSystemsWithApplications225(2023)120151

Maximumflowaccelerationbytraversingtreebasedtwo-boundarygraph contraction

WeiWei

a

,

b

,PengpengWang

a

,

b

,YaboDong

c

,

?

aKeyLaboratoryofGrainInformationProcessingandControl(HenanUniversityofTechnology),MinistryofEducation,Zhengzhou450001,China

bHenanProvincialKeyLaboratoryofGrainPhotoelectricDetectionandControl,HenanUniversityofTechnology,Zhengzhou450001,China

cCollegeofcomputerscienceandtechnology,ZhejiangUniversity,Hangzhou310027,China

ARTICLEINFO ABSTRACT

Keywords:

Tree-cutmappingBoundarynodeMaximumflowGraphcontractionOverlay

Themaximumflow(max-flow)problemissofundamentalthatthecorrespondingalgorithmshavemanyapplicationsinmanyscenarios.Acommonaccelerationstrategyistoreducegraphsizebycontractingsubgraphs,buttherearefewcandidatesubgraphswithnosizelimitthatcanguaranteeexactmax-flowsolutionsaftercontraction.Weaddanewsubgraphcontractionconditiontotheexistingconditionswithcorrespondingefficientlocatingalgorithm,andweproposeamax-flowaccelerationalgorithmusingtraversingtree-basedcontraction(TTCMax).TTCMaxcanworkefficientlyonlybyusingconnectivityinformation.Throughdepth-firsttraversing,itcancontracttwo-boundarygraphsofanysizeintoedges,andthenaccelerateexistingmax-flowalgorithmsusingcontractedgraphs.Large-scalerandomandreal-worldgraphexperimentstestitseffectandtheaccelerationratiocanbemorethan50timeswithlowgraphreductionoverhead,indicatingthattheproposedalgorithmcanbeusedasaneffectivecomplementtoexistingalgorithms.

Introduction

Asafundamentalandwidelyinvestigatedproblem,themaximumflow(max-flow)problemanditsdualproblem,theminimumcut(min-cut)problemhavemanyapplicationsandareoftenusedassubroutinesinotheralgorithms(

Sherman

,

2009

).Manyadvanceshavebeenmade

in

thedevelopmentofefficientalgorithmsforthisproblem(

Goldberg

&Rao

,

1998

).Fastsolutionscanbefoundthroughalgorithm-orientedacceleration(

Boykov&Kolmogorov

,

2004

;

Goldberg&Tarjan

,

2014

;

Verma&Dhruv

,

2012

),orgraphdata-orientedacceleration(

Gusfield

,

1990

;

Wei,Liu,&Zhang

,

2018

;

Zhang,Hua,Jiang,Zhang,&Chen

,

2011

;

Zhang,Xu,Hua,&Zhao

,

2012

;

Zhao,Su,Liu,&Zhang

,

2014

;

Zhao,Xu,Hua,&Zhang

,

2012

).Asfordata-orientedalgorithms,thecoreideaistoreducethesizeoftheinput,suchasreducingthesizeofthegraphbycontractingsubgraphstonodes.Therearemanycontraction-basedalgorithmsthatexploitvarioussubgraphcontractionconditions.Unfortunately,mostofthesealgorithmscanonlyobtainapproximatedvaluewhenusingsubgraphcontractionconditionwithnosizelimit.

Inthepaper,weproposealosslessalgorithmthatemploysasub-graphcontractionconditionwithnosizelimit,andatoyexampleisgivenin

Fig.

1

toclarifythedifferencebetweentheproposedmethodandexistingcontraction-basedmethods.Unlikeexistingnode-orientedcontractions,theproposedalgorithmcontractssubgraphsintoedges.

Thecorepartisaroutinethatcanefficientlysearchforthetwo-boundarygraph(TBG),thatis,thesubgraphcontainingtwoboundarynodesthatseparateitfromotherpartsofthewholegraph.Experimentsvalidateitseffectivenessbyusinglarge-scalegraphscontainingupto107nodes.

Theworkadvancesthestateoftheartbyintroducinganewlosslessandgeneralsize-freecontractionconditionwithahighlyefficientwaytolocatethecorrespondingsubgraphs.Specifically,thetheoreticalcon-tributionsinclude:(a)Weprovethatthecontractionoftwo-boundarygraphscanmaintaintheexactmax-flowresult,whichleadstothecontractionalgorithmthathasfewconstraints(e.g.,unlimitedsubgraphsize)andcanensureaccuratesolution.Theseconditionshavehardlybeenmetsimultaneouslybefore.(b)Tofindthetwo-boundarygraph,weproposetousethemappingbetweenthedepth-firsttraversaltreeandthenodecutset(NCS).ThemethodcanefficientlysearchfortheNCScontainingonlytwonodes(i.e.,twonodesoftheboundedgraph).

(c)WeproposethestrategyofselectingallreusableTBGsforagivennodepair.

Inaddition,thepracticalcontributionsare:(a)Toensurealgorithmgenerality,weproposetoidentifythebi-connectedcomponent(BCC)firstandthenTBGineachBCC,toensurealgorithmgenerality.SinceTBGpartiallyoverlapswithsomeexistingandinefficientsubgraph

?Correspondingauthor.

E-mailaddresses:

weiwei_ise@

(W.Wei),

wangpengpeng_do@

(P.Wang),

dongyb@

(Y.Dong).

/10.1016/j.eswa.2023.120151

Received10June2022;Receivedinrevisedform11March2023;Accepted12April2023

Availableonline20April2023

0957-4174/?2023ElsevierLtd.Allrightsreserved.

W.Weietal.

ExpertSystemsWithApplications225(2023)120151

2

Fig.1.ExamplesshowingthedifferencebetweenTTCMaxandexistingcontractionalgorithms(usedinSection

1

).

contractionconditions,itcannotbeapplieddirectly.(b)Toensurealgo-rithmefficiencyandavoidthehighcomplexityofenumeratingTBGs,weintroducealowcomplexityrandomsearchalgorithm,whichcanhelpfindenoughTBGsforaccelerationatasmallcost.Experimentalresultsshowthatthealgorithmcanaccelerateexistingalgorithmsingeneratedgraphfamiliesandreal-worldgraphs,whiletheaccelerationratiocanbeuptotwoordersofmagnitude,andthuscanbeusedasaneffectivecomplementtoexistingalgorithms.

Literaturereview

Classicaccelerationattemptsmainlyfocusedonalgorithmtuning.Existingalgorithmsevolveintwodirections:theaugmentingpath-basedalgorithms(

Jack&Richard

,

1972

)andpreflow-basedalgo-rithms(

Goldberg&Tarjan

,

1988

).Theaugmentingpath-basedalgo-rithmsfocusonhowtofindasuitablepathbetweensourceandsinknodesineachiterationofmax-flowcomputation,sothatthewholecomputationcanbeefficientlyaccelerated.

JackandRichard

(

1972

)

W.Weietal.

ExpertSystemsWithApplications225(2023)120151

providedselectionrulesthatcanhelpavoidimproperselectionofaugmentingpathsleadingtoseverecomputationaldifficulties.Anewalgorithmusingtheshortestaugmentingpathwasproposed.

Karzanov

(

1974

)explicitlyintroducedtheblockingflowmethod,whichaug-mentedalongamaximumsetofshortestpathsbyfindingablockingflow.Suchaugmentationincreasedtheshortestaugmentingpathlengthandthusacceleratedtheshortestaugmentingpathmethod.Unlikeaug-mentingpath-basedmethods,push-relabel-basedmethodsmaintainedapreflowanditerativelyappliedpushoperationstoupdatethepreflow,

and

usedrelabeloperationstoupdatenodedistances(

Goldberg&

Tarjan

,

1988

).Here,apreflowisdifferentfromaflowinthatthetotalamountflowingintoanodecantemporarilyexceedthetotalamountflowingout,andtheproposedalgorithmpushesthelocalflowexcesstowardsthesinkalongtheestimatedshortestpath.

Inadditiontotuningalgorithmsthatkeepexactmax-flowvalues,

there

isalsoresearchintotradingaccuracyforspeed.

Christiano,Kel-

ner,Madry,Spielman,andTeng

(

2011

)proposedanewapproximationalgorithmforthemax-flowproblem.Bysolvingalistofelectricalflowproblemswiththesolutionofalinearequationsystem,thealgorithmcanbefasterthantheprevious??(??3∕2)algorithms.

Sherman

(

2013

)proposedanewalgorithmusing??-congestion-approximators.Theal-gorithmmaintainedanarbitraryflowthatmayhavesomeresidualexcessanddeficits,andittookstepstominimizeapotentialfunctionmeasuringthecongestionofthecurrentflowplusanover-estimate

of

thecongestionrequiredtoroutetheresidualdemand.

Jonathan,

YinTat,Lorenzo,andAaron

(

2014

)introducedanewframeworkforapproximatelysolvingflowproblemsandappliedittoprovideasymptoticallyfasteralgorithmsformax-flowandmaximumconcur-rentmulti-commodityflowproblems.Thetechniquestheyusedareanon-Euclideangeneralizationofgradientdescentwithboundsonitsperformance,thedefinitionandefficientconstructionofanewtypeofflowsparsifier,andafastobliviousroutingschemeforflowproblems.

Anothermajorcategoryofmax-flowaccelerationalgorithmisbasedonpreprocessing,i.e.,reducingthegraphsizeforacceleration.Specialsubgraphsarecontractedtohelpreducethesizeofthegraph,butcanalsocauseachangeinthemax-flowvaluebetweennodepairs.Therearemanydifferentsubgraphcontractionconditionsthatcanbeusedtocontractthegraph.Thefirsttypeofcontractionconditionistomaintainthemax-flowvaluesintheoriginalgraph.

ScheuermannandRosenhahn

(

2011

)proposedanalgorithmforimagesegmentation,andthebasicideaistosimplifytheoriginalgraphwhilemaintainingthemax-flowproperties.ThealgorithmconstructsaSlimGraphbymergingnodesthatareconnectedbysimpleedges,andtheresultingslimGraphcanbeappliedwithstandardmax-flowalgorithms.

LiersandPardella

(

2011

)presentedflow-conservingconditionsunderwhichsubgraphscanbecontractedtoasinglenode.Aftercapacitynormalization,thealgorithmattemptedtoshrinkthemaxedgeamongalledgesbetweentwonodes,orbetweenthreenodes,orbetweenaspecialclusterofnodes.Basedontheconditions,theresearchersalsoproposedatwo-stepmax-flowalgorithmtosolvetheprobleminstancesfromphysicsandcomputervision.

Therearealsographcontractionconditionswithnosizelimitthatcansignificantlyreducethegraphsizebutattheexpenseofchangedmax-flowvalues.

Zhangetal.

(

2011

)examinedthegraphcontractionconditionofmaximalclique.Bycontractingtheappropriatemaximumcliqueinthenetwork,thealgorithmcanapproximatethemax-flowresultefficiently.

Zhangetal.

(

2012

)leveragedthegraphcommunityforacceleration.Thecommunitydetectionalgorithmisappliedto

detectallcommunitiesinanetwork,wherethesourceandsinknodes

wereestablishedtofindneighbor-node-setastocontracttheoriginalgraphformax-flowacceleration.

Existingresearchhasalsoacceleratedmax-flowcalculationbycon-structingahigh-leveloverlay.Theoverlaypathcanhelpaccelerateordirectlyobtainmax-flowresults.Awell-knownoverlayistheGomory–Hutree(

Gusfield

,

1990

).Itisbuiltbyorganizingallthe??nodesoftheoriginalgraphintoatree,andtheminimumedgecapacityinthepathbetweenanytwonodesisthemax-flowvaluebetweenthem.TheGomory–Hutreeisnotwidelyusedduetoitshighcomplexity,e.g.,it

needs

???1max-flowcalculationtobuildaGomory–Hutree.

Zhao

etal.

(

2014

)viewedtheoriginalgraphasalayergraphbetweenthesourceandsinknodes,e.g.,nodesatthesamedistancefromthesourcenodeformalayer.Themax-flowvaluecanbecalculatedasthesmallestofallthemax-flowvaluesbetweenadjacentlayers.

Weietal.

(

2018

)attemptedtodividetheoriginalgraphintosubgraphs(i.e.,thebi-connectedcomponent)withcutnodesasboundarynodes.Max-flowcalculationbetweenanygivennodepairinvolvesonlyaportionofcutnodesandsubgraphs,anditcanbedividedintoseveralsub-calculationsbetweenadjacentsubgraphs.

Alltheabovemax-flowcalculationscanbefurtheracceleratedby

algorithm

parallelization(

Baumstark,Blelloch,&Shun

,

2015

;

Jiadong,

Zhengyu,

&Bo

,

2012

;

Khatri,Samar,Behera,etal.

,

2022

).

Khatri

etal.

(

2022

)proposedseveraltechniquestoimprovetheperformanceofthepush-relabelmax-flowalgorithmonGPUs.Theythencombinethepush-relabelalgorithmwiththeirnewlyproposedpull-relabelalgo-rithmtoconstructapull-push-relabelmaxflowalgorithm.Experimentsusingreal-worldandsyntheticgraphsshowitssignificantacceleration

ratio

inthreerepresentativemaximumflowapplications.

Baumstark

etal.

(

2015

)foundthatthewell-knownhighestlabel-basedpush-relabelimplementationisnotoptimalfortheircollectedbenchmarkinstances.Instead,thefirst-in-first-outpush-relabelalgorithmappearstobemoresuitableandisimplementedasasharedmemory-basedparallelalgorithm.Aparallelversionofglobalrelabelingisusedtoimprovespeed.Experimentalresultsshowthesuperiorityofthisalgo-rithmoverthefastestexistingimplementation.

Jiadongetal.

(

2012

)proposedtwoGPU-basedmaximumflowalgorithms,wherethefirstisasynchronousandlockfreeandthesecondissynchronizedviatheprecoloringtechnique.ExperimentalresultsshowthattheGPU-basedalgorithmoutperformstheCPU-basedalgorithmbyaboutthreetimes,andinGPU-basedalgorithms,thesynchronousalgorithmoutperformstheasynchronousalgorithminsomesparsegraphs.

Model

Themax-flowproblem

Themax-flowproblembetweennodes??and??inadirectedgraphisformulatedinEq.(

1

).??isthecollectionofallnodesinthegraph,and

??isthecollectionofalldirectededgesinthegraph.Foradirectededge

??fromnode??to??,denote????≥0asthecapacityof??,and??(??,??)≤????or

| |

??(??)≤????astheamountofflowfrom??to??,themax-flowproblemistofindthemaximumsumofflowoutof??andinto??,asshowninEq.(

1

).Here???(??)={??∈??(??,??)∈??}and??+(??)={??∈??(??,??)∈??}

aretwosetsofadjacentnodesof??.Theconstraintsoftheproblemare:

(∑

(a)theflowvalueoneachedgeshallnotexceedthecapacityoftheedge,and(b)thevalueofallflowsintoanodemustbethesameasthatoutsidethenode.Thesolutionisthemax-flowvalue???(??,??)andtheflowvaluesatalledges.Wemainlyfocusontheprobleminconnectedundirectedgraphs,whichcanberepresentedasdirectedgraphsbytransformingeachundirectededgeintotwodirectededgesbetweenadjacentnodes.

arenotdividedintoanycommunities.Foreachcommunityfoundinthenetwork,thealgorithmwillvalidatethecontractconditionthatthetotalamountflowingintoacommunitycanflowthroughthecommunity,whichwillbecontractedifconditionshold.

Zhaoetal.

???(??,??)=??????

??∈??+(??)

?

??0≤????≤???????∈??(??)

??(??,??))

(1)

(

2012

)examinedthegraphcontractionconditioncalledneighbor-node-set,whichisonenodeplusitsneighboringnodes.Specialconditions

??.??.

3 ??

??∈∑???(??)

??(??,??)=

∑

??∈??+(??)

??(??,??)???∈???{??,??},(??)

W.Weietal.

ExpertSystemsWithApplications225(2023)120151

PAGE

4

Definition3.5.Intheoriginalgraph,TBGcontractionistoreplaceallnodesandedgesintheTBGasanedgebetweenitstwoBNs,andtheedgecapacityisthemax-flowvaluebetweenBNsthroughnodesinsidetheTBG.

TBGcanhelpspeedupmax-flowcalculationbecauseTBGcontrac-tiondoesnotchangethemaximumflowvaluebetweenanynodesoutsidetheTBG.

Lemma3.6.ForaTBG,themax-flowvaluebetweenthenodepairsoutsidetheTBGintheoriginalgraphisthesameasinthegraphwiththecontractedTBG.

Fig.2.AnexampleofTBGdefinedin

Definition

3.4

(Allsolid-linenodesandtheedgesconnectingthemconstituteTBG).

Thebi-connectedcomponenttree

Givenanundirectedgraphof??withthesetofallnodes??andthesetofalledges??,wefirstintroducethecoredefinitionsthatarerelatedtoouralgorithm.Ifnotmentioned,allthegraphsmentionedareundirectedgraphs.

Definition3.1.Acutnodeinagraphisanodewhoseremovalwilldividethegraphintoatleasttwodisconnectedsubgraphs.Bi-connectedcomponent(BCC)isthemaximumconnectedsubgraphinwhichanytwonodeshaveatleasttwodisjointpathsbetweenthem.

NotethatthecutnodeswillsplittheoriginalgraphintoBCCs.Anexampleisshownin

Fig.

4

(a),whereanygraphcanberepresentedasthegraphontheleft,withtheBCCtreeontheright.Itisobviousthatremovinganycutnodewilldisconnectthegraph.IthasbeenfoundthatanygivengraphcanbetransformedintoaBCCtreewithcutnodeconnectingtheseBCCs(

Hopcroft&Tarjan

,

1973

)(asshownontherightof

Fig.

4

(a)):

Theorem3.2.AnyconnectedgraphcanbetransformedintoatreeofBCCs.

Proof.Pleaserefertopaper(

Weietal.

,

2018

).

Thetwo-boundarygraph

Thedefinitionofboundarynodeisintroducedfirst.

Definition3.3. Foraconnectedsubgraph??′in??withnodeset

??′???andedgeset??′???,aboundarynode(BN)of??′isanode

??∈??′thathasatleastoneadjacentnode??′∈?????′.

Inthepaper,wefocusonthekindofsubgraphthatcontainsonlytwoBNs.

Definition3.4.Thetwo-boundarygraph(TBG)isaconnectedsub-graphin??withonlytwoBNs.

AnexampleofTBGisgivenin

Fig.

2

,whereallsolid-linenodes(andtheedgesbetweenthem)constituteTBG.AnyothernodeexceptBNs(nodes1and2)intheTBGiscalledtheinnernode(IN),i.e.,allINsandBNsin

Fig.

2

constituteTBG.AnynodeoutsidetheTBGiscalledtheouternode(ON)oftheTBG.

TBGisusefulbecausebycalculatingthemax-flowvaluebetweenitsBNsinsidetheTBG,wecancontracttheTBGasanedgebetweenitsBNs,andtheedgecapacityisjustthemax-flowvaluebetweenitsBNsinsidetheTBG:

Proof.

Forthemax-flowprobleminanundirectedgraph,itneedstobeconvertedtotheproblemintheequivalentdirectedgraph,thatis,theundirectededgebetweentwonodesisconvertedintotwodirectededgesofthetwonodeswiththesamecapacityastheundirectededgecapacity.Anyin-edgeflowisadirectedflowwiththesamedirectionasthedirectededge.

Denotethemax-flowfrom??to??as???(??,??),giventwonodes??and??

intheequivalentdirectedgraphcorrespondingtotheundirectedgraph,itisshownbelowthatforeachpairofadjacentnodes??and??,onlyoneedgeof(??,??)and(??,??)hasapositiveflowvalueinthefinalmax-flowresult.

Becausethemaximumvaluesofvariousaccuratemaximumflowalgorithmsareconsistent,weuseoneofthecommonlyusedmethods,theaugmentingpath-basedmethod,toillustratetheaboveconclusion.Formax-flowfrom??to??,thecoreideaistofindandfillasimplepathwithpositivevalueflowbetween??and??ineachiterationuntilnofurtherpathcanbefoundaftermanyiterations.Thepathfindingisappliedtotheresidualgraphupdatedineachiteration.Forexample,intheoriginalgraphforthedirectededge(??,??)withitscapacity????(??,??)andflowvalue

????(??,??)afteraniteration,intheresultingresidualgraphtherewillbeanedge(??,??)with??(??,??)=????(??,??)?????(??,??),andanedge(??,??)with??(??,??)=????(??,??)+????(??,??).

Notethatintheaugmentingpath-basedmethod,theresidualcapacityof(??,??)introducedbytheflowonthereverseedgeisusedatfirst,andusingthecapacityofoneedgeintheresidualgraphdecreasestheflowvalueonitsreverseedgeintheoriginalgraph.Thus,inoneiteration,sincethesimplepathallowsnoloopingintheresidualgraph,onlyoneofthetwoedges(??,??)and(??,??)willbeincludedinthesimplepathbetween??and

??.Soafterthefirstiteration,onlyoneedgehasflowintheoriginalgraphandassumethatitisthedirectededge(??,??)withitscapacity????(??,??)andflowvalue????(??,??).Assumingthatinthenextiterationtheedge(??,??)isincludedinthepathwithflow

??(??,??),if????(??,??)≥??(??,??),intheoriginalgraphitwillcausetheflowvalueof(??,??)todecreasei.e.,(??,??)withupdatedflowvalue

????(??,??)???(??,??)and(??,??)withflowvalue0.

Orif????(??,??)<??(??,??),thenintheoriginalgraphtheflowvalueof(??,??)willdecreaseto0andtheflowvalueof(??,??)willbecomepositive??(??,??)?????(??,??).Theresultissimilarifedge(??,??)isselected,i.e.,onlyoneedgeofthetwoedgesbetweentwonodeshasapositiveflowvalueintheupdatedoriginalgraphofeachiteration.

Thus,itisobviousthatintheresultingoriginalgraphofeachiteration(includingthefinalresultgivenbythefinaliteration),onlyoneedgeof(??,??)and(??,??)isusedtoholdtheflow.

Giventwonodes??and??intheequivalentdirectedgraphcorre-spondingtotheundirectedgraph,when???(??,??)isdeployedinthegraph,???(??,??)withthesamemax-flowvaluecanbedeployedinthegraphatthesametime.

Accordingtoitem

(2)

above,thereverseedgeofeachpositive-flowedgeisnotusedinthemax-flowresult.Itisobviousthatfor

eachedge(??,??)withpositiveflowvalue??(??,??)inthemax-flow

Itisclearthat????≤???(??,??)and????≤???(??,??)inanymax-flow

1 12 2 21

resultbetween??and??,bymovingtheflowinedge(??,??)toedge

(??,??)withsameflowvalue(whichisequivalenttoreversingtheinandoutflowsofeachnode),theper-nodeflowconstraints

resultbetween??and??outsidetheTBG.Becauseanydeployed

flowsmustbefeasibletoreachthetargetnode??inthemax-flowresult.Orif????>???(??,??)anditmustflowoutofTBGthrough??2,

? 1 12

inEq.(

1

)alsoholdanditwillgeneratethemax-flowresult??(??,??)

withsamemax-flowvaluefromnodes??to??.Andsinceeachin-edgeflowof???(??,??)sitsatadifferentedgefromitscounterpartin

???(??,??),???(??,??)and???(??,??)onlysharenodesandthustheirflowswillnotaffecteachother,itisclearthat???(??,??)and???(??,??)canbedeployedinthegraphatthesametime.

DenotetheboundarynodeofthegivenTBGas??1and??2.Denotethemax-flowvaluebetween??1and??2as?????????,the

whichwillgenerateanin-edgeflowdistributionwiththetotal

flowvaluebetween??1and??2insideTBGlargerthan???(??1,??2)

and???(??2,??1),whichcontradictsthemax-flowdefinition.

Asaresult,iftheTBGiscontractedastheundirectededge(or

directededgesinbothdirections)between??1and??2withthemax-flowvalue???(??1,??2)==???(??2,??1),theflowsinto??1or??2inthemax-flowresultcanbekeptunchangedandthecapacitylimitis

met,sotheotherpartsofthemax-flowresultarekeptthesame.

???????

(??1,??2)

Inaddition,themax-flowvaluebetween??and??willnotincrease

??(??2,??1)withthesamemax-flowvaluecanbedeployedinthe

TBGatthesametime.

Thisisobviousfromtheitem

(3)

above.

Denotethemax-flowfrom??to??as???(??,??),giventwonodes??and??intheequivalentdirectedgraphcorrespondingtotheundirectedgraph,itisshownbelowthatthereisnocycleflowpathinthe

asthecontractionwillnotgenerateanynewaugmentingpathbetween??and??.Ifthebottleneckedgetofindamoreaug-mentingpathisnotinsidetheTBG,TBGcontractionwillkeeptheotherpartofthemax-flowresultandthebottleneckedgeunchanged,andthusnonewaugmentingpathwillbegenerated.IfthebottleneckedgeisinsidetheTBG,theremustbe????==

max-flowresults.Thatis,intheoriginalgraphthedirectededge

???

1

or??2==???

(??1,??2) 1

(??2,??1)(orTBGcanindependentlyadjustthe

withpositiveflowwillnotformacycle.

Supposethatwhenasimplepathbetween??and??(i.e.,??)isfoundintheresidualgraphinoneiteration,therewillbeacycleflowpathintheupdatedoriginalgraph.Supposeintheoriginalgraphthepathsegmentcontainingtheoverlappednodesinthelooppathandthesimplepathisboundedbynodes??and??.Itisclearthatthereareatleasttwodirectedpathsinreversedirectionswithpositiveflowbetween??and??intheoriginalgraph,anddenotethemas????(??,??)and????(??,??)andsuppose????(??,??)asthepathsegmentinthefoundsimplepathintheresidualgraph,whichisalsothesimplepathintheoriginalgraph.So,beforethesimplepath??isfound,????(??,??)alreadyexistsintheoriginalgraphandthereiscertainlyasimplepathwithresidualcapacitiesbetween??and??intheresidualgraph(i.e.,??(??,??)).Andnotalledgeshaveresidualcapacityinthe????(??,??)appliedintheresidualgraphortherewillbeacycleflowpathbeforethesimplepath

??.Thatis,givenapath??(??,??)withresidualcapacitiesinallitsedges,thealgorithmchoosesthepath????(??,??)withsomeedgesthatdonothaveresidualcapacitiesintheresidualgraph,whichcontradictsthefactthatintheaugmentingpath-basedmethod,residualcapacitywillbeusedfirst.Thus,inthemax-flowresultoftheoriginalgraph,thedirectededgewithpositiveflowwillnotformacycle.

Inthemax-flowresultbetweenanynodepair,??and??outsidea

TBGwithBN??1and??2,representtherespectiveflowvalueintotheTBGthrough??1and??2as????and????,onlyoneof????and????

internalflowtoallowmoreflowthroughtheTBG),sobykeepingtheedgecapacityaftercontractionas???(??1,??2),thecontractionwillnotgenerateanewaugmentingpath.

Asaresult,TBGcontractionwillmaintainthemax-flowresultbeforecontractionandwillnotgenerateanewaugmentingpathtochangethemax-flowresult.

Thelemmaisproved.

Asaresult,formax-flowcalculationbetweenanynodepairoutsidetheTBG,theTBGcanbetreatedasanedgebetweenitsBNs.AndforTBGsthatdonotcontainthegivennodepair,theycanbecontractedonebyonewhilethemax-flowvalueofthenodepairremainsun-changedaftereachcontraction.Thatis,allTBGsthatdonotcontainthegivennodepaircanbecontractedatthesametime.

ItisalsofoundthatfortheTBGinsideaBCC,theremainingportionoftheBCCafterremovingtheTBGisstillaTBG,whichisdefinedastheinverseTBGoftheoriginalTBG:

Lemma3.7.InaBCCwithnodeset???andedgeset???,givenanyTBGinsideitwithnodeset??′????andedgeset??′????withthesetoftwoboundarynodes????.TheBCCportionoutsidetheTBGwithnodeset

??′′=??????′+????andedgeset??′′=??????′isstillaTBGwiththesameBNs.

Proof.BecausethereareatleasttwopathswithoutdisjointingnodesbetweenanytwonodesinaBCC,neighborsaandbofboundarynodes

isgreaterthan0.

1 2 1

2 ??1and??2outsidetheTBGhavepathsthatdonotpassthrough??1and

Thus,ifboth????and????arenotzerointhemax-flowresult,since

??2.Byadding??1and??2andtheiredgeswiththerespectiveneighbors

1 2 ??and??,itwillgenerateapathbetween??1and??2intheBCCportion

theflowintotheTBGfrom??2canonlyexitTBGthrough??1