Average Delay of Routing Trees SaberMirzaei BostonUniversity January13,2016 6 Abstract 1 The general communication tree embedding problem is the problem of mapping a set of communicating 0 2 terminals,representedbyagraphG,intothesetofverticesofsomephysicalnetworkrepresentedbyatreeT. InthecasewheretheverticesofGaremappedintotheleavesofthehosttreeT theunderlyingtreeiscalled n a routing tree and if the internal vertices of T are forced to have degree 3, the host tree is known as layout a J tree. Differentoptimizationproblemshavebeenstudiedintheclassofcommunicationtreeproblemssuchas 2 well-knownminimumedgedilationandminimumedgecongestionproblems. Inthisreportwestudytheless 1 investigatemeasurei.e. treelength,whichisarepresentativeforaverageedgedilation(communicationdelay) measureandalsoforaverageedgecongestionmeasure. WeshowthatfindingaroutingtreeT foranarbitrary ] graphGwithminimumtreelengthisanNP-Hardproblem. C C . 1 Definitions and Introductory Points s c [ ConsideragroupofterminalscommunicatingviaafinitenetworkG=(V,E),wherethesetofvertices(finite 1 setV)andedges(finitesetE),respectivelyrepresentthecollectionofterminalsandtheirdirectcommunication v paths. Weshow∣V∣bynand∣E∣asm. 7 9 The general communication tree embedding problem is the problem of mapping the set of terminals into the 6 set of vertices of some physical network represented by a tree T. Accordingly, the two vertices v,u ∈ V(G) 2 that are directly connected via e ∈ E(G), are connected indirectly via some path P (v,u) in T. In the case 0 T . where the vertices of G are mapped to the leaves of the host tree, the underlying tree is called a routing tree. 1 0 Inthisreportwemostlyfocusonthecasewheretheinternalverticesofthehosttreehavedegree3(knownas 6 treelayout problem). WedenotethesetsofleafnodesandinternalnodesoftreeT respectivelybyV (T)and L 1 V (T). 1 : I v For a graph G and a communication tree T for G, there are different measures defined in literature. In i X followingwedefinethetwomeasuresthatweareintrustedinthisreport. Foracomprehensivelistofmeasures, r aninterestedreadercanreferto[3]. a Definition1.1(EdgeDilation). ConsideragraphGandacommunicationtreeT andabijectionϕfromvertices of G to leaf nodes of T. The dilation λ(uv,T,ϕ,G) of an edge {u,v} ∈ E(G) is the distance between ϕ(u) andϕ(v)inT. ◻ Werepresentthedistanceoftwovertices{u,v}inagraphGwithd (u,v) G Definition 1.2 (Edge Congestion). Give a graph G and a communication tree T and and a bijective mapping ϕ∶V(G)→V (T). Thecongestionδ(xv,T,ϕ,G)andofanedge{x,y}∈E(T)isthethenumberofedges L in{u,v}∈E(G)thatinT,thepathP (ϕ(v),ϕ(u))traversetrough{x,y}. ◻ T 1Wetrytousethetermnodeincaseoftreesasopposedtothetermvertex,whichweuseforgeneralgraphs. 1 Based on the definition of the communication tree for a graph G, removal of every edge {x,y} ∈ E(T) partitions the set of vertices of G into two component. Hence every edge of tree corresponds to a cut in G. Thereforethecongestionof{x,y}∈E(T)isthesizeofthecutitcorrespondsto. Several optimization problems can be defined based on these two measures. Minimum tree layout dilation is the problem of finding a tree layout for a given graph G such that the maximum edge dilation is minimized, wherethemaximumistakenoveralledgeofG. In[7]itisshownthattheproblemoffindingatreelayoutwith minimumdilationisNP-hard,whenthelayouttreeisrooted. Similarly, given a graph G, in minimum tree layout congestion problem the goal is to find a tree layout T, such that the maximum edge congestion is minimized. In [8] Seymour and Thomas show that the minimum tree layout congestion problem is polynomially solvable for the case of planer graphs, and is NP-hard when consideringgeneralgraphs. Inthisreportwestudytheminimumtreelayoutlengthproblem(shortlycalledMin TreeLength),formallydefinedasitfollows. Definition1.3(Minimumtreelayoutlength). ConsiderthefiniteundirectedgraphG = (V,E). Theminimum treelayoutlengthproblemistheproblemoffindinglayouttreeT andabijectivemappingϕ∶V(G)→V (T) L suchthatL(T,ϕ,G)=∑{u,v}∈E(G)λ(uv,T,ϕ,G)isminimized. ◻ It is not hard to see that ∑{u,v}∈E(G)λ(uv,T,ϕ,G) = ∑{x,y}∈E(T)δ(xv,T,ϕ,G). Hence, in the rest of this reportwemayusetheminterchangeably. Accordingly, in the communication graph embedding problems, the dilation of an edge {u,v} ∈ E(G) abstractly represent the communication delay between vertices u and v. Similarly the congestion of an edge e∈E(T)isarepresentativeforthetrafficonthephysicallinke. Hencetreelengthmeasurecorrespondstothe averagedelaybetweentheverticesofGandalsototheaverageedgecongestionofthehosttree. 2 Minimum Length of Tree Layout Inthespecialcaseoftreelayoutproblem,theunderlyinghostgraphisatreeT wherethedegreeofeverynode is either 1 or 3 and the vertices of G are being mapped to leaves of T. In this section we study minimum tree layoutlength. WeshowthatMinTreeLengthproblemisNP-hardformulti-graphs2,andlateronweshowthe problemstaysNP-hardwhenrestrictedtotheclassofsimplegraphs. 2.1 MinTreeLengthofCompleteGraphs ConsiderthecompletegraphG=(V,E)where∀u,v ∈V(G),{u,v}∈E(G). Itisnothardtoseethatalayout treeT isasolutionfortheMinTreeLayoutproblemforG, iff∣V (T)∣ = n(andhence∣V(T)∣ = 2n−1), and L thesummationofdistanceofleafnodesofT isminimized. Wedenotethesummationofdistancesofleavesof atreeT by: 1 σ (T)= ∑ d (x,y) LL T 2 x,y∈VL(T) Leaf to leaf distance summation measure σ is very similar to the definition of Wiener index (proposed by LL chemistWiener[10]),whichisthesummationofdistancesofallverticesofagivengraphGasrepresentedin followingequation. 1 σ(G)= ∑ d (u,v) G 2 u,v∈V(G) 2Bymulti-graphwerefertofinitegraphswithpossibilityofparalleledgesandnoloop. 2 Wiener index is widely studied both in mathematical and chemical literature. In [2] Fischermann et al. study Wienerindexoftrees. Inthisworksauthorsrepresentthestructureofthefamilyofthetreesthathaveminimum (ormaximum)Wienerindexamongallthetreesofthesameorderwithmaximumnodedegree∆ ≥ 3. Dueto similarityofσ measureandWienerindex,intherestofthissubsectionweborrowsomeofthenotationsand LL definitionsfrom[2]inordertostudyσ fortreeswithmaximumdegree∆. LL Definition2.1(T(R,∆)treefamily). Considerintegers∆andR∈{∆,∆−1}. Foragivenn∈N,thefamily T(R,∆)oftreeswithnnodeshasauniquememberTuptoisomorphism, definedusingaplanarembedding asitfollows. LetMk(R,∆)≤n<Mk+1(R,∆)where: ⎧ ⎪⎪1 k =0 M (R,∆)=⎨ k ⎪⎪1+R+R×(∆−1)+...+R×(∆−1)k−1 k ≥1 ⎩ Figure1depictstheembeddingoftreeTwiththefollowingproperties: 1. allnodesofTlieonsomelineL for0≤i≤k+1 i 2. exactlyonenodev liesonthelineL whichhasmin{n−1,R}childrenonlineL 0 1 3. fori=1tok−1everynodeonlineLi isconnectto∆−1nodesonlineLi+1 andonenodeonlineLi−1 4. theonlylinethatmaybeincomplete,islineLk+1. Letn−Mk(R,∆)=m×(∆−1)+rfor0≤r<∆−1, wheren−Mk(R,∆)isthenumberofremainingnodesonlineLk+1. Alsolet{v1,..vm+1}bethesetofm leftmostnodesonlineLk wherevm+1 istherightmostoneintheset. Eachofv1,..vm nodesisconnected to∆−1nodesonlineLk+1,whilevm+1 isconnectedtor nodesfromlineLk+1 (seefigure1). ◻ … … Lk+1 Lk V1 V2 Vm Vm+1 … … … L2 L1 L0 Figure1: PlanarembeddingofTrepresentedastheembeddingofnodesonk+2linesL for0≤i≤k+1. i We defined the family T(R,∆) for the general case of trees with maximum degree ∆, while we focus on the case where the degree of every internal node is ∆ = 3, but all the results presented in the rest of this subsectionextendtoalltreeswitharbitrarymaxdegree∆≥3. 3 Lemma 2.2. Consider tree T ∈ T(R,∆) of order n, and assume Mk(R,∆) < n < Mk+1(R,∆) for k ≥ 1. LetT beanarbitrarytreeofordernconstructedfromtreeT ∈T(R,∆),withM (R,∆)nodes,byattaching 0 k n−M (R,∆)nodestotheleafnodesofT (whichlieonthelineL ). Thenitisthecasethateitherσ (T)> k 0 k LL σ (T)orT isisomorphicwithT. LL Proof. WeproofthislemmausinginductionontheheightoftreeT,whenembeddedontheplaneasexplained in definition 2.1. It is easy to check the correctness of theorem for trees of height 1 and 2. Assume tree T of heightk andtreeT ∈T(R,∆)arenotisomorphic. Letv ∈V(T)bethenodeonlineL . Nodev isconnected 0 toRsubtrees{T1,...,TR}. BasedontheassumptionofinductioneverysubtreesTiisamemberofthefamily T(∆−1,∆) of height k or k−1. Since T and T are not isomorph, there are at least two subtrees T and T i j for i ≠ j where are incomplete on line L . Formally speaking ∃1 ≤ i ≠ j ≤ R,T ,T ∈ T(∆−1,∆) and k i j ∣V(Ti)∣−Mk−1(∆−1,∆)=ri >0∧∣V(Tj)∣−Mk−1(∆−1,∆)=rj >0. Withoutlossofgeneralityweassume i=1andj =1andalso∣V(T )∣≤∣V(T )∣. Figure2aabstractlyrepresentstreeT. 1 2 L L k k L L T T k-1 T T k-1 1 2 1 2 L L 1 1 L L 0 v 0 v ′ (a)InitialtreeT. (b)TreeT constructedfromT. Figure2: Figure2arepresentstreeT ∉T(R,∆)ofheightk+1,constructedfromtreeT ∈T(R,∆)ofheight 0 k. Nodev isconnectedtoatleasttwosubtreesT ,T ∈T(R,∆)ofheightk whichareincompleteonlineL . i j k ′ AlternativetreeT depictedinfigure2b,isconstructedbyrelocatingsomeleafnodesofsubtreeT thatareon 1 lineL . Asyouseeinthisconstructionr leftmostleavesofT arerelocatedtocompletesubtreeT . Inthis k 2 1 2 examplethenumberofleafnodesofT onL ,islargeenoughtocompletethesubtreeT . 1 k 2 ′ Let L (T) denote the set of nodes of tree T on line l. We present an alternative tree T , by relocating some l leaf nodes of L (T ) (in order from left to right) to complete the line L of T (in order from right to left). k 1 k 2 ′ Let L ⊆ L (T ) be the set of leaf nodes of T on line L , candidate for relocation. Figure 2b depicts tree T k 1 1 k constructedfromT. ′ ′ InthealternativetreeT ,considerabijectivemappingϕ fromthenodesofT tonodesofsubtreeT ,where 0 1 2 ′ T is the modified version of T in T. More specifically, mapping ϕ is a reflection form T to T , which 2 2 0 1 2 ′ reflectsnodesofLl(T1)tothenodesofLl−1(T2)for2≤l≤k,suchthattheleftmostnodeonlineLl ofT1 is ′ mappedtotherightmostnodeofT onlineL . Accordinglyϕ mapseveryleafnodeofL=L (T )−L(the 2 l 0 k 1 set of remaining leaf nodes of T on line L ) to one leaf node of T on line L . On the other hand every leaf 1 k 2 k nodeofLk−1(T1)ismappedtoonenode(leaforinternal)ofT2 onlineLk−1. ′ From ϕ we construct a bijective mapping ϕ from leaf nodes of T to sets of leaf nodes of T . For every 0 1 2 ′ w ∈V (T),ϕ(w)={ϕ (w)}ifϕ (w)∈V (T )isaleafnodenode,otherwise(ϕ (w)isaninternalnodeof L 0 0 L 2 0 ′ T2 onlineLk−1),ϕmapsw tothesetofdirectchildrenofϕ0(w)onlineLk 3. ′ Using the bijective mapping ϕ, we analyze the change in value of σ in the process of constructing T from LL T asitfollows. 1. ClearlytheinternalsummationofdistancesofnodesinLstaysunchanged. 3Inthiscase∣ϕ(w)∣≤∆−1. 4 2. Foreveryleafnodew1 ∈L,w2 ∈VL(T)−VL(T1)⊎VL(T2),itisthecasethatdT(w1,w2)=dT′. Hence, thesummationofdistancesamongnodesinLandleafnodesofV (T)−V (T )⊎V (T )alsodoesnot L L 1 L 2 change. 3. Weshowthatforeveryw ∈Lthesummationofdistancesofw fromleafnodesofV (T )⊎V (T )− 1 1 L 2 L 1 ′ ′ {w }isgreaterthanthesummationofdistancesofϕ(w )fromleafnodesofV (T )⊎V (T )−{ϕw }. 1 1 L 1 L 2 1 Notation 2.3. Let L ,L ⊂ V(T), for an arbitrary tree T. By σ (L ,L ) we denote the summation of 1 2 T 1 2 distancesofnodesofL andL . Formallyspeaking: 1 1 1 σ (L ,L )= ∑ ∑ d (v,u) T 1 2 T 2 v∈L1u∈L2 Foreveryw ∈V (T )−L: 2 L 1 • Ifw2 isonlineLk,itisthecasethatdT(w1,w2)=dT′(ϕ(w1),ϕ(w2)). Therefore: (1) σ ({w },{w }⊎ϕ(w ))=σ ({ϕ(w )},{w }⊎ϕ(w )) T 1 2 2 T 1 2 2 ′ • Ifw2 isonlineLk−1 andϕ(w2)mapsw2 toaleafnodeofT2 onlineLk−1,similartopreviouscase wehave: (2) σ ({w },{w }⊎ϕ(w ))=σ ({ϕ(w )},{w }⊎ϕ(w )) T 1 2 2 T 1 2 2 ′ • Otherwisew2 isonlineLk−1 andϕ(w2)mapsw2 toanon-emptysetofleafnodeofT2 onlineLk. Assumethesizeofthissetis1 ≤ ∇ ≤ ∆. Sinceforsomenodesw where∣ϕ(w )∣ = ∇ = ∆−1 > 1, 2 2 thenforsuchw ,thefollowingequallyholds: 2 (3) σT({w1},{w2}⊎ϕ(w2))−σT′({ϕ(w1)},{w2}⊎ϕ(w2))= (d (w ,w )+2k×∇)−(2k+(d (ϕ(w ),ϕ (w ))+1)×∇)= T 1 2 T′ 1 0 2 (d (w ,w )+2k×∇)−(2k+(d (w ,w )+1)×∇)= T 1 2 T 1 2 (2k−d (w ,w ))×(∇−1)−d (w ,w ))≥ T 1 2 T 1 2 2k−2d (w ,w ))>0 T 1 2 ′ Putting the results of previous cases and equations 1, 2 and 3, we conclude that σ (T) > σ (T ). If LL LL ′ ′ ′′ T ∉T(R,∆),thenbasedontheassumptionofinduction,replacingthesubtreeT withsubtreeT ∈T(R,∆) 1 1 1 ′′ ′′ ′ ofthesameorder,resultsintreeT ,whereσ (T )<σ (T ). LL LL ′′ UsingthesameapproachandcontinuingwithT ,inasequenceofleafnoderelocations,wecanconstructthe finaltreeT̃, suchthatinT̃, nodev onlineL hasexactlyoneincompletesubtreeT̃ whereT̃ ∈ T(∆−1,∆). 0 i i Morespecifically, ∀1 ≤ l < i, allleafnodesofT̃ leionlineL and∀i < l ≤ ∆, allleafnodesofT̃ leionline l k l Lk−1,i.e. T̃∈T(R,∆). Notation2.4. GivenanarbitrarytreeT,wedefinetheplanarlineembeddingofT similartothetheapproach inthedefinition2.1. Startingfromadesignatedv ∈ V(T),weembedT onlinesofplane,wherev liesonline L anddirectneighboursofv areplacedonlineL . Similarlyallthenodesindistancedfromv areplacedon 0 1 line L . Also for u ∈ V(T) on line L , the subtree rooted at u, where all its nodes are on lines L for l′ ≥ l is d l l′ denotedbyT . Formallyspeakingw∈V(T )iffuisontheshortestpathfromw tov onlineL . u u 0 5 Notation2.5. ConsideratreeT ofordernandanodev ∈V(T)ofdegree∇. RemovingvformT partitionsT n intoasetofsubtrees{T1,...,T∇}. Wecallnodev centralif∀1≤i≤∇,∣V(Ti)∣≤ . Thesetofcentralnodes 2 oftreeT isrepresentedbyC . T Theorem2.6. EveryarbitrarytreeT hasatleastoneandatmosttwocentralnodes. Inotherword1≤∣C ∣≤2. T For proof see [9]. Using this theorem, we proof the main result of this subsection as we present in the theo- rem2.7. Theorem 2.7. Consider tree T with maximum node degree ∆. where σ (T) ≤ σ (T′) for every tree T′ LL LL (that∣V (T′)∣=∣V (T)∣). ThenintheplanarlineembeddingofT withcentralnodev ∈C onfixedlineL ,it L L T 0 isthecasethat: • T ∈T(∆,∆) • T ∈T(∆−1,∆)foru≠v u Proof. The proof of this theorem is carried out using induction on the height of planar line embedding of tree T. Itisnothardtocheckthecorrectnessoftheoremfortreesofheight1and2. LetT beagraphofheighth≥3, andletu ,...,u bethedirectneighboursofv onlineL andT ,...,T respectivelybetheircorresponding 1 ∆ 0 1 ∆ subtrees. Case 1: ∃w ,w ∈ V (T),d (w ,v) ≥ d (w ,v)+2. Based on the assumption of induction w and w 1 2 L T 1 T 2 1 2 can not be on the same subtree. Without loss of the generality assume w and w are the two leaf nodes with 1 2 maximumdistanceandw1 ∈T1 andw2 ∈T2. LetT11,T12,...,T1,∆−1 ⊂T1 besubtreesrespectivelywithroots u11,...u1,∆−1 connectedtou1 (nodesu11,...u1,∆−1 lieonlineL2). Alsoassumew1 ∈VL(T11). Case1.1: ∣V (T )∣>∣V (T )∣. WeconstructanalternativetreeT̃byremovingedges{u ,u }and{v,u } L 11 L 2 1 11 2 and introducing two new edges {v,u } and {u ,u }. The structures of initial tree T and the alternative tree 11 1 2 ̃ T are represented in figure 3. One can verify that the following equation 4 correctly represents the relation T T 11 12 T T L u u 2 12 11 12 T T 2 2 3 L T T 2 u1 u2 u3 LL1 u11 u2 u1 u12 u3 L1 v 0 11 3 L 0 v (a)InitialtreeT whered (w ,v)≥ T 1 d (w ,v)+2forw ∈V (T )and (b) Alternative tree T̃ constructed T 2 1 L 11 w ∈V (T ). fromT. 2 L 2 ̃ Figure3: RepresentationofinitialtreeT anditsmodifiedversionT. 6 betweenσ (T)andσ (T̃). LL LL (4) σ (T)−σ (T̃)= LL LL ∣V (T )∣×( ∑ ∣V (T )∣− ∑ ∣V (T )∣) L 11 L 1i L i 2≤i≤∆−1 3≤i≤∆ +∣V (T )∣×( ∑ ∣V (T )∣− ∑ ∣V (T )∣) L 2 L i L 1i 3≤i≤∆ 2≤i≤∆−1 =(∣V (T )∣−∣V (T )∣)×( ∑ ∣V (T )∣− ∑ ∣V (T )∣) L 11 L 2 L 1i L i 2≤i≤∆−1 3≤i≤∆ Itisthecasethat∑2≤i≤∆−1∣VL(T1i)∣<∑3≤i≤∆∣VL(Ti)∣otherwiseitmustbethecasethat∣V(T1)∣>∑2≤i≤∆∣V(Ti)∣> ∣V(T)∣,whichisincontradictionwiththecentralityofnodev. Thereforeσ (T)−σ (T̃)>0,whichcon- LL LL 2 tradictstheoptimalityofT. Case 1.2: ∣V (T )∣ ≤ ∣V (T )∣. Hence, d (w ,v) = d (w ,v)+2 and w ∈ V (T ) is located on line L L 11 L 2 T 1 T 2 1 L 11 k andw2 ∈ VL(T2)liesonlineLk−2. AlsononofsubtreesT11 andT2 canbecompleterespectivelyonlinesLk andLk−1. LetL (T)denotethesetofnodesoftreeT onlinel. Similartotheproofoflemma2.2,wepresentanalternative l treeT̃,byrelocatingsomeleafnodesofLk(T11)(inorderfromlefttoright)tocompletethelineLk−1ofT2(in order from right to left). Let L ⊆ L (T ) be the set of leaf nodes of T on line L , candidate for relocation. k 11 11 k Basedonanexactreasoningasinlemma2.2(case3),whichweomit,itcanbeinferredthatthesummationof distanceofleafnodesinLfromleafnodesofT ⊎T reducesgoingfromT toT̃. Formallyitcanbededuced 11 2 that: (5) σT(L,VL(T11))+σT(L,VL(T2))>σT̃(L̃,VL(T̃11))+σT̃(L̃,VL(T̃2)) WhereT̃ andT̃ respectivelycorrespondtoT andT afterrelocatingleaf nodesofL(representedbyL̃in 11 2 11 2 ̃ T). Ontheotherhand,relocatingL,increasesthedistanceofeveryleafnodeinLfromleafnodeofT12,...,T1,∆−1 by 1 unit, while it decreases the distance of every node of L from every leaf node of T ,...,T . Since we 3 ∆ assumedthatw ∈V (T )andw ∈V (T )havethemaximumdistanceamongallleafnodes,then: 1 L 11 2 L 2 (6) ∣VL(T12)∣+...+∣VL(T1,∆−1)∣<∣VL(T3)∣+...+∣VL(T∆)∣ Fromequations5and6weconcludethefollowingcontradictoryresult: (7) σ (T)−σ (T̃)= LL LL σT(L,VL(T11))−σT̃(L̃,VL(T̃2))+ σT(L,VL(T2))−σT̃(L̃,VL(T̃11))+ σT(L,VL(T)−VL(T11)⊎VL(T2))−σT̃(L̃,VL(T̃)−VL(T̃11)⊎VL(T̃2)) >0 Case2: ∀w ,w ∈V (T),∣d (w ,v)−d (w ,v)∣<2. SincebasedontheassumptionofinductionT ,...,T ∈ 1 2 L T 1 T 2 1 ∆ T(∆−1,∆), then T can be constructed from some tree T ∈ T(R,∆) of order ∣V(T )∣ = M (R,∆), by 0 0 k attaching n − M (R,∆) nodes to the leaf nodes of T . Therefore, based on lemma 2.2, T is optimal iff k 0 T ∈T(∆,∆). Corollary2.8. ConsiderthecompletegraphGofordern=∣V(G)∣. TreeT isanoptimaltreelayoutforGiff ∣V (T)∣=nandT ∈T(3,3). L 7 Example 2.9. Let G be a complete graph of order n = 2l for some l > 1. Based on the result of theorem 2.7, alayouttreeT forG(oforder2n−1)hasminimumvalueσ (andaccordinglyisasolutionforMinLayout LL Length)iffitisisomorphictosometreewithastructuresimilartothetreeinfigure4. Figure 4: Two planar embeddings of an optimal layout tree T of size 2n−1, corresponding to the complete graphGwithn=2l vertices. 2.2 MinTreeLengthofMulti-Graphs Graph G is a multi-graph if either it is a simple undirected graph, or it can be constructed from a simple undirectedgraphbyaddingparalleledges. InourmainresultofthisreportweshowthattheMinTreeLength problem is NP-hard for class of multi-graphs. Finally we show that this result can be extended to the class of simplegraphs. Definition2.10(EqualSize4-CliqueCover). GivengraphG,EqualSize4-CliqueCoverproblemistheprob- n lem of partitioning V(G) into four disjoint subsets V ,...,V s.t. G(V ) is a clique of size , for 1 ≤ i ≤ 4 . 1 4 i 4 ◻ Lemma 2.11. Equal Size 4-Clique Cover problem is NP-complete, even for the class of graphs of order 2l verticesforsomel∈N. Forproofyoucanreferto[]. Theorem2.12. MinTreeLengthproblemisNP-hardfortheclassofmulti-graphs. Proof. The correctness of the theorem can be represented using a polynomial reduction form Equal Size 4- CliqueCover. ConsideranarbitrarygraphG,asaninstanceinputofEqualSize4-CliqueCoverproblem,where∣V(G)∣=2l for some l ∈ N. Let G′ be the multi-graph obtained from G by introducing M = m×(2n−2) parallel edges between every two vertices u,v ∈ V(G). Notice that every tree layout T for graph G has 2n−2 edges where the congestion of each edge is less than m = ∣E(G)∣. Considering graph G as an vertex induced subgraph of G′,thenG′ =G⊎G̃,whereG̃isanothervertexinducedsubgraphofG′. SubgraphG̃iscompletemulti-graph. HenceforeverytreelayoutT andϕ∶V(G)→V (T)forG′ wehave: L (8) L(T,ϕ,G′)=L(T,G)+L(T,ϕ,G̃) From corollary 2.8 we know that a layout tree T̃ for G̃ is optimal iff T̃ ∈ T(3,3). Also for every layout tree T ∉T(3,3),itisthecasethatL(T, G̃)≥L(T̃, G̃)+M. Ontheotherhandforn>2andeverylayouttreeT , , where∣V (T)∣=n,itisalwaysthecasethatL(T,G)<M. L 8 ′ ̃ ′ Therefore, a layout tree T for G is optimal iff T and T are isomorphic. In other words T for G is optimal iff T ∈ T(3,3). Hence the Min Tree Length problem for G′ reduces to the problem of finding an optimal bijection ϕ form vertices of G to leaf nodes of T̃ ∈ T(3,3), such that the summation of edge dilations for all {u,v}∈E(G)isminimized. Formallyspeaking: (9) argmin L(T,ϕ,G′)=(T̃,argminL(T̃,ϕ,G)) (T,ϕ) ϕ LetGdenotethecomplementofgraphG. Onecaneasilycheckthat: (10) L(T̃,ϕ,G)=L(T̃,ϕ,K )−L(T̃,ϕ,G) n WhereK isacompletegraphofsizen.Therefore: n (11) argminL(T̃,ϕ,G)=argmaxL(T̃,ϕ,G)=argmax ∑ λ(uv,T̃,ϕ,G) ϕ ϕ ϕ {u,v}∈E(G) AlsobasedonthestructureofT̃,∃c1,c2 ∈CT̃(infigure4shownbydoublelinedcircles). Sincen=2l forl∈N, ̃ removingcentralnodesc andc partitionleafnodesofT into4equallysizedpartitionsL ,...,L . 1 2 1 4 n Finally, we can deduce that the original graph G can be partitioned into 4 complete sub-graphs of size , iff 4 thereexistbijectionϕsuchthat∀{u,v}∈E(G),ϕ(u)∈L ∧ϕ(v)∈L for1≤i≠j ≤4. Inotherwords,graph i j G can be partitioned into 4 complete sub-graphs G ,...,G of size n, iff (T̃,ϕ) is a solution for Min Tree 1 4 4 LengthofG′,whereϕmapsverticesofG toleafnodesofL for1≤i≠j ≤4. WhichinferstheNP-hardness i i ofMinTreeLengthproblemforthemulti-graphs. 2.3 MinTreeLengthofSimpleGraphs Finite graph G′ is simple, if for u ≠ v ∈ V(G′) there is at most one edge {u,v} ∈ E(G′) and ∀u ∈ V(G),{u,u}∉E(G). Considercompletemulti-graphG,whereeverytwoverticesuandvareconnectedvial paralleledges. Havingmulti-graphGonecanobtainasimplegraphG′bysubdividingveryedge{u,v}∈E(G) andintroducinganewvertexxofdegree2. ConsideratreelayoutT′ andbijectivemappingϕ′ ∶ V(G′) → V (T′)forthesimplegraphG′. Foreveryx ∈ L V(G′),ϕ′(x)∈V (T′)isdirectlyconnectedtosomeinternalnodew∈V (T′). Removingwresultsintheset L I ofthreesubtree{T′ ,ϕ′(u),T′ }. Foreveryx∈V(G′),byT′(x)andT′(x)wereferrespectivelytosubtree w,1 w,2 1 2 T′ andT′ , wherew isthedirectneighbourofϕ′(x)inT′. Itiseasytoseethatσ({ϕ′(x),w},T′,ϕ′,G′) w,1 w,2 isequaltothedegreeofxinG,andalsoifxisofdegree2thenthecongestionofthetwoedgesconnectingw toT′ andT′ isequaliffϕ′(u)∈V(T′ )andϕ′(v)∈T′ ,whereuandv arethedirectneighborsofxin w,1 w,2 w,1 w,2 G. Consider tree layout T and bijective mapping ϕ ∶ V(G) → V (T) for the multi-graph G. Starting from tree L ′ ′ T, we can constructed a new tree T for the simple graph G by subdividing some edge of T and introducing ′ sub-treelayoutscontainingonlyverticesofdegree2. Inotherwords,T isconstructedfromT byintroducing m = ∣E(G)∣internalnodeandmleafnodes(eachcorrespondingtoonevertexofG′ ofdegree2). Figures 5a and 6a respectively depict the multi-graph G and its corresponding tree layout T, while in figures 5b and 6b ′ ′ ′ youcanseesimplegraphG obtainedfromGandonepossibletreelayoutT forsimplegraphG constructed fromT. Lemma2.13. LetGbeacompletemulti-graphwhere∀u,v ∈V(G)thereexistlparalleledge{u,v}∈E(G). ′ LetT andϕbearbitrarytreelayoutandthecorrespondingmappingforG. AlsoassumeG isthesimplegraph ′ obtainedbysubdividingeveryedgeofG. WeshowtheclassofallpossiblelayouttreesforG ,constructedfrom T byF(T). ConsidertreelayoutT′ ∈F(T),where∀T′′ ∈F(T),LA(T′,G)≤LA(T′′,G). Thenitisthecase ′ that T is constructed by subdividing only edges of T that each one is adjacent to a leaf node (which we call 0 externaledges). 9 1 2 12 1 2 21 23 14 13 31 24 42 41 32 3 4 34 3 4 43 (a) Complete multi-graph G where everytwoverticesareconnectedvia (b) Simple graph G′ obtained from l=2paralleledges. G. ′ Figure5: SimplegraphG obtainedfromGbysubdividingeveryedgeofGandintroducingavertexofdegree 2. Proof. We know that for every edge e ∈ E(T),σ(e,T,G) ≥ l×(n−1) where n = V(G) and equality holds onlyifeisadjacenttoaleafnodew ∈V (T). NowconsideranarbitraryT′′ ∈F(T),obtainedbysubdividing L atleastoneinternaledgee∈E(T)4. Itiseasytocheckthat∀e∈E (T),σ(e,T,G)≥l×2×(n−2). Asappose I ′′ ′ ′ to tree layout T for G , we suggest tree layout T constructed by relocating the subtree (possibly more than one subtree) that subdivides e (and hence removing all the subdivisions of e) and creating a new subdivision (possiblymorethanonesubdivision)inaanexternaledge{w,w′}(assumew∈V (T)). Wechooseanexternal L edge{w,w′}suchthatfortheeveryleafnodexoftherelocatedsubtree, {ϕ−1(x),ϕ−1(w)} ∈ E(G′). Hence ′ ′′ basedontheconstructionofT formT ,thefollowingequationholds,whichinturnevidencesthecorrectness ofthelemma. LA(T′′,G′)−LA(T′,G′)>(l×2×(n−2))−(l×(n−1))>0 From the result of lemma 2.13 one can infer the fact that given layout tree T and mapping ϕ for complete ′ multi-graph G, an optimal tree layout (based on T) for simple graph G can be constructed by subdividing onlyexternaledgesofT andintroducingsub-treelayoutscorrespondingtothenewverticesofdegree2. Butit doesnotprovideanyinformationregardingtheexactstructureoftheoptimaltree. Inwhatfollowsandwithout ′ providingallthedetailsoftheproof,wepresentthestructureoftheoptimallayouttreeforG ,constructedfrom T. Notethatforthesakeofthemaintheoreminthissubsection,wedonotneedtoknowtheexactstructureof thethreelayoutwithminimumtreelength. n(n−1) ThesimplegraphG′containsexactlyl× verticesofdegree2. Everyvertexv ∈G′ofdegreel×(n−1)is 2 directlyconnectedtol×(n−1)verticesofdegree2. TheoptimaltreelayoutT′obtainsfromT,bysubdividing every external edge {w,w′} ∈ E (T) (where w ∈ V (T)) exactly once with a sub-tree layout containing E L l ×(n−1) leaf nodes5. Every leaf node of this subtree correspond to one vertex x ∈ V(G′) with degree 2 2 wherexisdirectlyconnectedtow. 4 Edge e ∈ E(T) is external if it is adjacent to a leaf node of T, and internal otherwise. Let E (T) and E (T) respectively I E representthesetofinternalandexternaledgesofT 5Forthesakeofthemaintheoreminthissection,weassumelisaneveninteger. 10