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