UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

D-width, metric embedding, and their connections Ali Safari, Mohammad 2007

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
ubc_2007-319208.pdf [ 4.5MB ]
Metadata
JSON: 1.0052053.json
JSON-LD: 1.0052053+ld.json
RDF/XML (Pretty): 1.0052053.xml
RDF/JSON: 1.0052053+rdf.json
Turtle: 1.0052053+rdf-turtle.txt
N-Triples: 1.0052053+rdf-ntriples.txt
Original Record: 1.0052053 +original-record.json
Full Text
1.0052053.txt
Citation
1.0052053.ris

Full Text

D-Width, Metric Embedding, and Their Connections by M o h a m m a d A l i Safari M . M a t h . , University of Waterloo, 2003  A THESIS S U B M I T T E D IN P A R T I A L  FULFILLMENT OF  THE REQUIREMENTS FOR THE DEGREE OF  D o c t o r of Philosophy  '  . -  in THE FACULTY OF GRADUATE  STUDIES  ( C o m p u t e r Science)  The University of British Columbia September 2007 © M o h a m m a d A l i Safari, 2007  Abstract E m b e d d i n g between metric spaces is a very powerful algorithmic t o o l and lias been used for finding good a p p r o x i m a t i o n algorithms for several problems. In p a r t i c u l a r , e m b e d d i n g to an £\ n o r m has been used as the key step i n an a p p r o x i m a t i o n algo-  -  r i t h m for the sparsest cut p r o b l e m . T h e sparsest cut p r o b l e m , i n t u r n , is the main" • ingredient of many algorithms that have a divide and conquer nature and are used i n various fields. W h i l e every metric is embeddable into l\ w i t h d i s t o r t i o n O ( l o g n ) [13], and  -"'  the b o u n d is tight [39], for special classes of metrics better bounds exist. Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into t\  [41], Series-parallel graphs [28] and A;-outerplanar graphs [19] (for constant A:) are  embeddable into i\ w i t h constant distortion, planar graphs and b o u n d e d tree-width --graphs are conjectured to have constant distortion in e m b e d d i n g to l\.  Bounded-  tree-width graphs are one of most general graph classes on w h i c h several h a r d p r o b lems are tractable.  -'  We s t u d y the e m b e d d i n g of series-parallel graphs (or, more generally, graphs w i t h tree-width two) into i\  and also the embedding between two line metrics.—""  We then move our attention to the generalization of tree-width to digraphs and hypergraphs and study several relevant problems.  Contents  Abstract  ii  Contents  i"  List of Tables  vii  List of Figures  vii  1  Acknowledgements  x  1  Introduction  1  1.1  Metric Embedding  1  1.1.1  2  1.2  Important Metrics  £i M e t r i c s  3  1.2.1  3  A n application  1.3  Line Metrics  •  1.4  Directed Metrics  10  1.5  B o u n d e d tree-width graphs and digraphs  10  1.5.1  U n d i r e c t e d Tree W i d t h  11  1.5.2  Directed Tree W i d t h  12  1.5.3  D i r e c t e d tree-width and Directed M e t r i c s  13  iii  8  1.5.4 1.6  2  Hyper-D-width . . .  14  Organization  15  t\ embedding of series-parallel graphs  16  2.1  Introduction  16  2.2  C o n s t r u c t i n g the embedding  17  2.3  Flattening  20  • 2.4 D i s t o r t i o n 9.0  3  • .  24  2.5  D i s t o r t i o n 6.0  25  2.6  Lower b o u n d  2.7  C o n c l u s i o n and Future W o r k  31  2.8  P r o o f of L e m m a 4  32  •.  29  Embedding between Line Metrics  40  3.1  Introduction  40  3.2  Preliminaries  3.3  Forbidden Permutations  44  3.4  E m b e d d i n g between two line metrics  45  •  42  3.4.1  Algorithm  .  3.4.2  Largest Eigenvalue  46  3.4.3  Bounding d  48  k  45  3.5  C o m p u t i n g Separability  49  3.6  P a t t e r n m a t c h i n g for permutations  3.7  Sortable Permutations •  53  3.8  Conclusions and Future W o r k  55  iv  -50  4  D-Width  57  4.1  Introduction  4.2  Definitions . ,.  60  4.2.1  D-width  60  4.2.2  Directed tree-width and haven order  62  4.2.3  C o p s and robber game  64  4.3  57  D i r e c t e d O n e Trees 4.3.1  4.4  "...  66  A l g o r i t h m i c results  '•.  C o m p a r i n g D-width and directed tree-width  72  4.4.1  A r b i t r a r y gap between different games  73  4.4.2  A r b i t r a r y gap between D-width, directed tree-width, a n d haven order  4.5  5  76  U p p e r B o u n d s for D-width 4.5.1  4.6  70  C o m p u t i n g the strongly cop-monotonicity  C o n c l u s i o n and Future W o r k  . .  78  '. . . .  80 82  Hyper-D-width  83  5.1  Introduction  •  83  5.2  Background  83  5.3  Hyper-D-width  87  5.3.1  Definition  87  5.3.2  Basic Properties  88  5.3.3 . Stability  88  5.3.4  Comparison  90  5.3.5  cops and robber game  92  .5.3.6  Applications  93 v  5.4  6  Introducing hyper-T-width  96  5.4.1  Properties  98  5.4.2  Computation  '  99  Conclusions and Research Directions  103  6.1  (\ metrics .  104  6.2  L i n e metrics  6.3  D-width  105  6.4  Hyper-D-width . . . ."  105  •  . .  Bibliography  ••••  104  107 v  VI  List of Tables 3.1  D i s t o r t i o n of TTI for several values of A:  3.2  d,,.  :  -  49 49  vii  List of Figures 2.1  T h e graph G '  2.2  F l a t t e n i n g a triangle. T h e right figure is really two degenerate triangles. 21  2.3  A pair of flattened triangles in a triangle sequence f r o m x to an a n -  x e  for e = ( s , i ) 6  20  6  cestor edge w i t h endpoint y.  C o n s i d e r i n g this case provides some  i n t u i t i o n for our stronger., parameterized, inequality  26  2.4  Lower b o u n d example  30  3.1  T h e 4-separable p e r m u t a t i o n ( 2 . 4 . 1 , 3 )  44  3.2  Algorithm  3.3  I l l u s t r a t i o n of p e r m u t a t i o n TX\-  48  3.4  A separation tree  51  3.5  5-sortable p e r m u t a t i o n ( - indicates coupling)  4.1  A d i g r a p h (left) w i t h its D-decomposition of w i d t h one (right).  4.2  G r a p h on which 4 cops have a w i n n i n g strategy but 5 cops are required  . 0  :  54  ;  ...  for robber-monotone strategy 4.3  4.4  46  61  75  G r a p h on w h i c h 4 cops have a robber-monotone w i n n i n g strategy but 5 cops are required for cop-monotone strategy  75  F i n d i n g a strongly cop-monotone w i n n i n g strategy  81  viii  5.1  A hyper-D-decomposition w i t h w i d t h two  5.2  Solving decomposable problem P on a bounded hyper-D-width hypergraph  :  87  95  ix  Acknowledgements T h i s thesis a n d m y entire career owes a lot to many people. I want to take the o p p o r t u n i t y to thank t h e m all for their support and encouragement w i t h o u t which I could not reach where I a m . T h r o u g h o u t m y P h D I have benefited from invaluable help that I received f r o m m y supervisor, Professor W i l l i a m Evans. I h a d regular weekly meetings w i t h h i m d u r i n g which I learned a lot from his insightful comments a n d b r i l l i a n t m i n d and learned how to discuss scientific problems and how to efficiently do research. W i l l generously shared w i t h me his valuable experience i n research a n d helped me do m y P h D research. I would like to deeply thank h i m for the o p p o r t u n i t y that I had to have h i m as m y supervisor. I a m grateful to m y supervisory committee members, Prof.  David Kirk-  patrick a n d Prof. P a v o l H e l l , w h o helped me d u r i n g the p r e p a r a t i o n of this thesis. I w o u l d like to thank D a v i d , Pavol, a n d also the university examiners, Prof.  Joel  F r i e d m a n a n d Prof. R i c h a r d Anstee for carefully reading the dissertation a n d for their valuable comments for i m p r o v i n g it. Before coming to U B C , I studied at the university of W a t e r l o o a n d at Sharif university of technology.  I have learned a lot. by w o r k i n g w i t h Prof..  Prabhakar  Ragde, A l e x L o p e z O r t i z , Therese B i e d l , M o h a m m a d G h o d s i , a n d J afar H a b i b i a n d a m grateful to th e m. M y time i n U B C couldn't be as successful w i t h o u t h a v i n g so many great a n d supportive friends. T h a n k y o u A r m i n , A l i r e z a , B a h a r a k , B a h r a i n , H a m i d , Hossein, M a h s a , M a j i d , M o h s e n , R a m i n , R e z a , Saeid, Yaser, Z a h r a , a n d many others whose name is missing for all your help a n d support. 21 years of continuous s t u d y i n g wouldn't have been possible without the support of m y great d a d , m o m , sisters a n d brothers. I missed t h e m ever since I came to C a n a d a , b u t they always supported me by regularly t a l k i n g to me o n the phone a n d praying for my success. Last, b u t definitely not least, one person has given the most effort d u r i n g these 4 years: m y dear wife, M a r y a m . She made our home a very happy place to  "i  live a n d always helped to relieve all of the stresses around me. T h i s thesis is dedicated to m y parents, brothers, a n d sisters, t o .my  dear  M a r y a m , a n d to my dear M a n a , m y little daughter. C r e d i t s . P a r t s of chapter 4 are based o n a n ongoing c o l l a b o r a t i o n w i t h P a u l Hunter.  M O H A M M A D A L I SAFARI  The University of British Columbia August 2007  xi  Chapter 1  Introduction T h e purpose of this chapter is to introduce metric embedding, directed tree-width and study their connections.  Its content is a mixture of background information,  newest research results i n the literature on relevant topics, a n d a s u m m a r y of our results which are fully explained in other chapters of the thesis.  1.1 A  Metric Embedding  metric M = (X, d)  X  is a set of points  w i t h non-negative distance function, d  defined o n any pair of points w i t h the constraint that the distances should satisfy the triangle inequality, i.e.  d(x,y) < d(x,z) + d(z,y),  for. all  x, y,  and  z\  moreover,  distances are symmetric, i.e. d(x, y) = d(y, x) for all x a n d y, a n d d(x, x) = 0, for allx . 1  Remark 1. Throughout this thesis, we may specify a metric M — (X,D) by its distance function D whenever X is clear from the context. So, we may write a metric D which, in fact, means a metric whose distance function is D. 1  I n a metric,  d(x,y)  is zero if and only if  x = y.  If we remove this constraint and allow  zero distance between different points then the metric is called a 1  semi-metric.  A n embedding f r o m one metric A — (XA,CLA) into another metric B — (XB,OIB) is a m a p p i n g / f r o m XA  t o XB- T h e expansion of /, denoted by  is the largest expansion over all distances, i.e. sup^, y  exp(f),  ^J^l'y-j ^ • T h e contraction  dB  y  of embedding /, denoted b y con(f), is the largest contraction over all distances, i.e. sup  d (?(x) f(y)) • V  x y  B  distortion of embedding / is defined as exp(f) x con(f).  D u r i n g the last decade or so, low d i s t o r t i o n embedding between metrics has been used extensively t o design efficient a p p r o x i m a t i o n algorithms. T h e reason is simple: Some problems P are easily solvable if their i n p u t comes f r o m some metric class B b u t are h a r d for inputs f r o m some other metric class A. If one can embed an i n p u t metric i n A t o a new metric i n B w i t h low d i s t o r t i o n and solve P o n the new metric a n d translate the result o n the original metric, this usually yields a n a p p r o x i m a t i o n a l g o r i t h m for metrics i n A-  1:1.1.  Important M e t r i c s  Some metrics are of particular interest for researchers because of their role i n f i n d i n g a p p r o x i m a t i o n algorithms, or their connection t o other interesting problems (see the survey by P i o t r I n d y k  [33]).  E v e r y edge-weighted, undirected g r a p h defines a metric  where the points i n the metric are vertices i n the graph a n d the distance between two 'points is the shortest p a t h length between the corresponding vertices.  Notice  that every metric corresponds to a complete graph w i t h edge weights equal t o the distance between edge end points. Some i m p o r t a n t metric classes of this type are those derived f r o m planar graphs (that correspond t o shortest paths of weighted planar graphs), trees, outer-planar graphs, /c-outer-planar graphs, a n d b o u n d e d treew i d t h ' graphs. A n o t h e r t y p e of metric that appears frequently i n the literature is if metric  2  w h i c h is the set of points i n M where for any two points X = d  Y  =  (xi,x , • • •, Xd) 2  a  n  d  0/i> 2/2, • • • j yd) the distance between t h e m is defined as .  \\X-  Y\\ =-tf\x! -yi\  k  k  + \x - V2\ + --- + \x - y \ k  k  2  d  for k — oo, \\X - YWoo = max-fjzi - yi\, \x - 2/21, • • • ,\ d~ x  2  d  (1.1.)  Vd\}- I n particular, the  l\ metric, for its close connection w i t h cut problems, the £2 or E u c l i d e a n metric, for its familiarity, a n d the £ o o , for its s i m p l i c i t y of c o m p u t a t i o n , are of interest for many researchers. Note that we use £^ instead of £f when dimension is not a concern. . E m b e d d i n g s between various i m p o r t a n t metrics have been studied before. For example, every n-point metric is isometrically embeddable(i.e. w i t h d i s t o r t i o n 1) into £00, t h o u g h w i t h many dimensions ( O ( n ) ) , a n d is embeddable into the £k metric w i t h d i s t o r t i o n O ( ^ ) [13, 39].  1.2  li Metrics  T h e r e are several reasons w h y £\ metrics are i m p o r t a n t to study. O n e m a i n reason is their close connection w i t h the multi-commodity flow problem a n d its d u a l version, the sparsest c u t problem. W h i l e the m a x i m u m m u l t i - c o m m o d i t y flow problem is solvable i n p o l y n o m i a l time, the sparsest cut problem is k n o w n t o b e . N P - h a r d [24]. In general, i f for any length assignment of edges o n a given g r a p h the associated shortest p a t h metric c a n be embedded into £\ w i t h d i s t o r t i o n .a, then the sparsest cut p r o b l e m ' c a n be solved o n that graph w i t h a p p r o x i m a t i o n factor at most a[28].  1.2.1  A n application  In this section we show how embedding a graph metric into the £\ metric is used to o b t a i n a n 0(logA;) a p p r o x i m a t i o n for the sparsest c u t p r o b l e m w i t h k t e r m i n a l 3  pairs [6]. L e t G = (V, E) be a n undirected graph w i t h capacities o n its edges. G i v e n k t e r m i n a l pairs  (SJ,£J)  (i = 1,2, ••• ,k), S j , i j e V , a n d A: r e a l v a l u e d demands, derrii,  the goal is t o find a cut  S, a subset of V , that minimizes the value C(S)/dem(S),  where C ( 5 ) is the t o t a l capacity of edges between S a n d S — V — S and dem(S) is the t o t a l d e m a n d of those pairs  (si,U) that have one node i n S a n d one i n S, i.e.  | { s t , t i } n s | = 1. J u s t like t h e m a x i m u m flow m i n i m u m c u t relationship, there is a generalized m a x i m u m c u t p r o b l e m that corresponds t o the sparsest c u t p r o b l e m . the  In  concurrentflowproblem (or d e m a n d flow problem) k t e r m i n a l pairs, (si,£j) for  i — 1, 2, • • • ,k, are given each having an associated d e m a n d , derrii for the i - c o m th  modity. T h e goal is to find the m a x i m u m fraction A a n d concurrently routed flows, while respecting edge capacity constraints, such that the flow corresponding to each c o m m o d i t y is at least A times their demands. O n e easy way t o m o d e l this is b y considering t h e flow associated w i t h every p a t h between c o m m o d i t y pairs. L e t Pi be the set of all paths f r o m Si to £j. L e t p\ be the j  th  p a t h i n Pi a n d j\ be the flow  routed t h r o u g h i t . T h e linear p r o g r a m is then as follows.  <d > e  Maximize  A subject to  E  <c  Ve  > Xdemi  V'i  Pi  eep{  <<Pi> Hjfi  e  (LPl)  T h e d u a l of LP\ is as follows.  Minimize  Y J e ^ e subject to  E id  ><Pi  Y^idemifi  >1  eep  .i,  e  c  e  V(z,j) •  4  V'i  (LP2)  O n e can view d ' s as distances o n edges. T h e first set of inequalities means e  <fi is at most the shortest p a t h value from S{ t o t;. A s we better have tpi as large as possible i n the second set of inequalities, the above L P reduces t o  Y"\ c d ^  Minimize  e  e  (LP3)  e  >1  Y dem d{si,ti) Ji  where  i  V'i  d(si,U) is the shortest distance between Si a n d i j defined b y d 's. e  E q u i v a l e n t l y we c a n s i mp l i f y LP3 as m  , . T){d)  m  d is a metric o n G where  C(d) = Y J c d a n d D(d) = e  Let  e  (1.2)  Y,i=i-k i ( i' i)dem d s  e  t  OPT* be the solution to ( L P 3 ) . For any p a r t i t i o n (S,V — S) the t o t a l ca-  pacity of edges between S a n d V — S is C(S) a n d there is a t o t a l d e m a n d of dem(S) for commodities that have |{sj,i;} f l S\ = 1. Hence, the m a x i m u m fraction of dem a n d s that can simultaneously be satisfied is at most  C(S)/dem(S). Consequently,  the m i n i m u m sparsest c u t is at least OPT*. L e t d be a distance f u n c t i o n o n the vertices of G such that there exists a set  S a n d for every edge e = {x,y} G EQ, d = d(x,y) = 1 i f exactly one of x a n d e  y is i n S, a n d is 0, otherwise. Such a distance f u n c t i o n d defines a cut metric o n the vertices of G. O n e c a n write the sparsest cut p r o b l e m as a linear p r o g r a m m i n g p r o b l e m as follows.  '  •  •  .  d  mm defines a cut-metric  V)d(x,y) C{d) —= 2^ i... dem d(si ti) D(d)  E(x, )eE  '  —  y  iz=  k  i  „.  (1.3)  )  If we relax the c o n d i t i o n that d defines a c u t metric a n d allow i t t o be any l\ metric then the answer w o u l d be the same because of the following two lemmas.  5  Definition 1. Given m metrics M\ = (X,di), M2 = (A, c^), •••, M — (X,d ), m  m  their sum, M = M\ + M2 + • • • + M is a metric (X, d) such that for any pair (x, y), m  d(x, y) = YliLi di(x, y). M is a positive weighted sum of metrics Mi, M2, • • • , M  m  if there exist positive values  w\,W2,  • • • ,w  such that d(x,y) = YliLx idi{x,y) for w  m  all pairs (x,y). Lemma 1 (Folklore). Every t\ metric can be written as a weighted sum of cut metrics. Proof. E v e r y i\ metric is a s u m of line metrics (i.e. l\ metrics) that correspond t o each dimension. So, i t suffices t o prove it for line metrics. A s s u m e that M is a line metric of n one-dimensional points x\, X2, • • • ,x  n  a n d x\ < x% < • • • < x . L e t Si be n  a cut metric i n w h i c h the distance between points p a n d q (where p < q ) is one only Hp <'i a n d q > i a n d is zero, otherwise. L e t a. = x.i \ — xi. W e c l a i m that M c a n L  be w r i t t e n as  +  aiSi. L e t p a n d q be two points and p < q. T h e distance between  points p a n d q is x — x = YJ?=p i which is equal to their distance i n YJj c^Sj. a  q  v  El  Lemma 2. For positive real values ai, ai, (5i(i = 1,2, • • • , n), mm — < = * — —  * Pi  2^i iPi a  Proof. L e t A = min* f,. T h e n , Y \ 0 * 0 4 > A 7^a,;A:- Hence, ^ '.•  ;  > A.  •  . L e t 8 be a n &\ metric that minimizes the value ^|^y over a l l £\ metrics.  A c c o r d i n g t o L e m m a 1 we c a n write 8 as a weighted s u m of cut metrics. L e t  8 = wi8\ -f- W282 + • • • + w 8 m  Hence, C{8) = J2Zi i ( i) w C 5  m  a  n  where each c\ is a cut metric and tUj's are all positive. d  ()  D  s  = J2Zi i ( i)w D 6  Therefore, according t o  L e m m a 2, there exists some index j such that jjfi^ < T$j- Since 8 minimizes t h e  6  value j£r^ over a l l l\ metrics (that include cut metrics as well) we conclude that DW) ~ D(S) • Consequently, we can formulate the sparsest cut p r o b l e m as a m i n i m i z a t i o n p r o b l e m over t\ metrics as follows.  I2(x,y)eE ( >y) ( >y) c  mm  x  d  — - —  d is a n t\ norm- 2_a=i--fc «  '  x  — e m  r -  n  „  (1.4)  i " ( i , U) s  B y L e m m a s 1 a n d 2, the value of (1.4) is equal to (1.3) a n d a solution t o (1.3) can be easily obtained f r o m any solution to (1.4). L e t OPT be the answer t o the sparsest cut p r o b l e m . A s mentioned before,  OPT> OPT*. L e t d* be the corresponding distance f u n c t i o n t o OPT*. H o w m u c h does  OPT* differ f r o m OPT? A c c o r d i n g t o B o u r g a i n ' s theorem  [13] d* can be embedded into some l\ metric d  +  with distortion O ( l o g n ) .  loss of generality assume that the embedding f r o m d* to d  +  OPT > OPT* = _ ^° *f > Y dem d*(s ,ti) i  Ced  i  Ecedj  >  .  >  0 ( l o g n) Y, dem d {s ,t ) +  i  Hence, d  +  :  has no expansion. So,  ^ * derm d*(si,U  ed  J  Without  l  l  OPT 0 ( l o g n)  gives a n O ( l o g n ) a p p r o x i m a t i o n for the m i n i m u m sparsest cut.  Notice that what is i m p o r t a n t i n the above inequality is the m a x i m u m con-  t r a c t i o n of distances  d (si,ti). +  W i t h a slight m o d i f i c a t i o n t o the embedding a l -  g o r i t h m one c a n use B o u r g a i n ' s theorem a n d make a n e m b e d d i n g that is not a n expansion a n d guarantees that the contraction for only t e r m i n a l vertices is not more t h a n 0(log&:), where k is the number of terminals. So, we c a n improve the a p p r o x i m a t i o n factor t o 0(log/c). See [6] for more details.  7  In order t o improve the a p p r o x i m a t i o n factor, one need only improve the d i s t o r t i o n of the embedding into £\. F o r some graphs, i n particular unit-weight expander graphs, this is n o t possible and the O ( l o g n ) b o u n d for the d i s t o r t i o n is tight [39]. Several researchers have then tried to find better d i s t o r t i o n for various classes of graphs.  P l a n a r graphs a n d b o u n d e d tree-width graphs are two widely  k n o w n classes that are conjectured to be embeddable into £\ w i t h constant distortion.  R a o [43] proves distortion 0{r  \/\og n) for any K ^  3  graphs. T h i s yields  r  r  m i n o r free class of  0(\/\og n) for planar graphs and b o u n d e d tree-width graphs.  O u t e r p l a n a r graphs are a class of graphs that are isometrically embeddable into £\. G u p t a et a l . [28] show that the distortion for series-parallel graphs is at most 7 + 4\/3 ~ 13.928. W e have improved this value to 6.0 and proved a lower b o u n d 3.0 for the e m b e d d i n g a l g o r i t h m provided by G u p t a et al.. L a t e r , C h e k u r i et al. [19] prove that fc-outer planar graphs can be embedded into r a n d o m trees, and hence into £\, w i t h constant d i s t o r t i o n , namely,  0(c ), for some constant c. F i n a l l y , C a r r o l et k  al. [16] recently found a low distortion embedding into £\ for b o u n d e d b a n d w i d t h graphs.  1.3  Line Metrics  A simple and interesting subclass of l\ metrics are line metrics. A line metric is a set of points on a real line w i t h distances measured using the £\ n o r m (using any £  k  n o r m , is equivalent). T h u s , line metrics are one dimensional versions of £\ metrics (£\)- Because of their s i m p l i c i t y and their many applications, line metrics are often the target metric for low d i s t o r t i o n embedding. B a d o i u et a l . [9] consider the p r o b l e m of embedding a fixed graph metric into the best.line metric. T h a t is, the authors choose the p o s i t i o n of the points o n 1  '  8  a line to m i n i m i z e distortion. For the case that G is unit-weighted and has an o p t i m a l line embedding w i t h d i s t o r t i o n c, they propose a 0 ( n c ) time a l g o r i t h m that finds an e m b e d d i n g w i t h 3  d i s t o r t i o n 0 ( c ) . Since they can always find an embedding w i t h d i s t o r t i o n 0{n) 2  (in  linear time) the best of these two embeddings gives an 0 ( y n ) - a p p r o x i m a t i o n for /  the o p t i m a l embedding. For unit-weighted trees, they propose an embedding w i t h d i s t o r t i o n 8A\/c  log c + 4c where A is some parameter k n o w n to be at most c. T h i s  yields a d i s t o r t i o n 0 ( n has r u n n i n g time an 0(n )  1 / / 3  ) i n g e n e r a l . T h e y also provide an exact a l g o r i t h m w h i c h 2  . In case that G is weighted and c = 1 + e < 1.5, they o b t a i n  a l g o r i t h m that finds an embedding / w i t h d i s t o r t i o n 1 + 0 ( e ) .  2  L a t e r on, B a d o i u et al.[8] consider the problem of embedding metrics corres p o n d i n g to weighted graphs into the line. L e t the m i n i m u m inter-point distance be 1 and the m a x i m u m be A . T h e y propose an approximate e m b e d d i n g w i t h distort i o n 0 ( A / c / ) and c ° W 3  4  n  4  for embedding general weighted graphs and weighted  trees^ respectively. For the latter case, they prove that it is h a r d to approximate the o p t i m a l e m b e d d i n g by  Q(^/n). In all cases, c is the o p t i m a l d i s t o r t i o n . We discuss  this result further i n Section 3 K e n y o n et al. [36] consider the problem of o p t i m a l l y e m b e d d i n g one line metric into another fixed one.  fixed  T h i s problem is different from w h a t we have  seen so far i n the sense that the target metric is fixed and one only needs to find the right m a p p i n g between points i n the i n p u t and target metrics. Such a problem has applications i n shape m a t c h i n g and object recognition. K e n y o n et al. propose a d y n a m i c p r o g r a m m i n g based a l g o r i t h m that computes the o p t i m a l embedding i n time 0 ( n  1 2  ) i n case the d i s t o r t i o n is less than 3 + 2\/2 ~ 5.829. We later describe  0 means a rough approximation of 0 with log factors ignored. For example, n l o g n = 0(n). 2  9  a f a m i l y of d y n a m i c p r o g r a m m i n g algorithms that compute o p t i m a l embeddings i n p o l y n o m i a l time provided the d i s t o r t i o n is less t h a n 13.60. T h e latter result was independently found by K e n y o n et al. i n an extension of their conference paper and also by C h a n d r a n et al. [17].  1.4  Directed Metrics  T h e r e are several problems whose u n d e r l y i n g metric is not necessarily symmetric. A t r i v i a l example is o p t i m i z a t i o n metric problems o n directed graphs such as f i n d ing a shortest p a t h . T h e r e have been some recent attempts to extend s y m m e t r i c (undirected) metrics t o asymmetric (directed) ones. Inspired by the directed version of cut problems, C h a r i k a r et a l . [18] study directed metrics for the first time a n d propose directed invariants of i\ metrics, t\ metrics, and some other metrics a n d study, their relationship w i t h directed c u t metrics.  1.5  Bounded tree-width graphs and digraphs  Tree-width has m a n y connections to what we have talked about so far. F o r l\ m e t r i c s , ' i t is conjectured that b o u n d e d tree-width graphs are embeddable into t\ w i t h constant d i s t o r t i o n . G u p t a et al. [28] show that the d i s t o r t i o n for series-parallel graphs (and, i n fact, for all graphs w i t h tree-width 2) is at most 7 + 4a/3 ~ 13.928. Trees, that have tree-width one, are also isometrically embeddable into t\.  For t h e  multi-cut p r o b l e m , C a l i n e s c u et al. [15] provide a p o l y n o m i a l time a p p r o x i m a t i o n 3  scheme ( P T A S ) for b o u n d e d degree and b o u n d e d tree-width graphs a n d digraphs. T h e multi-cut problem is related to the sparsest cut problem. In the multi-cut problem, there are k pairs of terminals and the aim is to delete edges of minimum total weight to disconnect all terminal pairs. 3  10  In this section we review the definitions of tree-width for graphs and digraphs and discuss some related results.  1.5.1  Undirected Tree Width  T h e n o t i o n of tree-width is considered as a generalization of trees (trees have treew i d t h 1) a n d many intractable problems are efficiently solvable o n b o u n d e d treew i d t h graphs.  E x a m p l e s include H a m i l t o n i a n cycle, graph i s o m o r p h i s m , vertex  coloring, and edge coloring. . A  tree-decomposition of a n undirected graph G = (V, E) is a pair (T, W),  where T is a tree, and W is a function that assigns to every node i of T a subset Wi of vertices of G such that  2. F o r each edge (u, v) € E, there exists some node i of T such that {u, v} C W j . 3. For- all nodes i, j, k i n T , if j is on the unique p a t h f r o m i t o k then Wi Pi  C  W. 3  T h e width of a tree-decomposition (T, W) is the m a x i m u m of \Wi\ — 1 over a l l nodes  i of T. T h e tree-width of G is the m i n i m u m w i d t h over all tree-decomposition  ofG. Notice that the above conditions c a n be interpreted as follows.  F o r any  connected set S of G, (Gl)  T\ : = {t\W n S ± 0} ^ 0, a n d  (G2)  T h e s u b g r a p h of T w i t h vertex set T\  s  t  s  forms a connected subtree of T .  11  and edges { ( s , t ) | W D W D 5 ^ 0} s  t  It c a n be easily shown that it suffices that the conditions G l a n d G 2 be true for only edges a n d vertices, i.e. m i n i m a l connected sets. A connected set S is m i n i m a l if there do not exist connected proper subsets A and B of S such that A U B = S and  A n B ^ 0.  1.5.2  Directed Tree Width  In 1996 R e e d et a l . [46] proved Youngers's conjecture [53] roughly saying that every directed g r a p h has either a large set of disjoint directed circuits or a s m a l l set of vertices that cover a l l directed circuits. I n their paper, they defined a version of well-linked sets for directed graphs and since the size of the largest well-linked set i n undirected graphs has close relationship w i t h tree-width [45] they suggested that the analogous definition of tree-width for directed graphs might be very useful, as pointed out i n [44]. W e believe that a proper definition should ideally measure t h e global connectivity of a d i g r a p h . F o r example the tree-width of a directed acyclicg r a p h ( D A G ) should be s m a l l because it has low connectivity. U n f o r t u n a t e l y finding a definition for directed tree-width analogous t o the undirected case is not easy, since almost all concepts related t o undirected tree-width behave differently i n directed graphs. [For example, the bramble number is equal to the haven order i n undirected graphs, while they may differ by a factor of two i n directed graphs [48].] There is not a n agreed-upon generalization of tree-width for directed graphs. For the first time Johnson, R o b e r t s o n , Seymour, a n d Thomas[34] gave a f o r m a l definition of directed tree-decomposition (called  arboreal-decomposition i n  t h e i r ' p a p e r ) a n d directed tree-width, a n d proved some theorems relating directed tree-width a n d haven order.  Other researchers proposed different definitions for  12  the directed tree-width. Safari [47] introduces D-width as a n alternative definition for directed tree-width and proved some facts to justify his definition as a proper measure for directed tree-width.  Definition 2 (D-decompositions and D-width). A D-decomposition of a di-  rected graph G is a pair (T,W) where T is a tree and W = {Wt\t E V(T)} is a family of subsets ofV(G) such that for every strongly connected set S C V{G): r  (Dl) T\ := {t\W n S + 0} + 0, and s  t  (D2) The subgraph of T with vertex set T\  s  and edges {(s,t)\W n W n S ^ 0} s  t  forms a connected subtree of T. A subset S of vertices of G is strongly connected if G[S] is strongly connected. The width  of a D-decomposition (T,W) is the minimum k such that \Wi\ < k + 1 for  all Wi 6 W. The D-width of a directed graph G is the minimum width over all D-decompositions of G. In C h a p t e r 4 we further extend these results and o b t a i n lower and upper bounds for D-width i n terms of certain cops/robber games o n digraphs and other parameters defined o n digraphs. W e also characterize the class of digraphs whose D-width is one.  1.5.3  Directed tree-width and Directed Metrics  T h e fact that b o u n d e d treerwidth graphs have a close relation w i t h l\ metrics quickly brings t o m i n d that b o u n d e d tree-width digraphs might have good connections t o directed metrics. B o u n d e d tree-width digraphs are actually k n o w n t o be connected to cut problems: Calinescu'et al. [15] propose a P T A S for b o u n d e d degree, b o u n d e d tree-width digraphs for the directed m u l t i c u t p r o b l e m on unit-weighted graphs. A 13  directed m u l t i c u t i n a d i g r a p h is a set of edges (or vertices i n the vertex version) whose removal leaves no strongly connected component containing b o t h vertices of a t e r m i n a l pair ( s j , i j ) .  1.5.4  Hyper-D-width  T h e way that D-width is defined suggests that it c a n be extended t o hypergraphs. In a D-decomposition of a d i g r a p h G, the subtrees corresponding to vertices of every strongly connected set S must form a connected subtree together. S is, i n fact, taken f r o m the set of m i n i m a l connected units of d i g r a p h G. If G was undirected then S was any edge or any vertex. I n case of hypergraphs, the m i n i m a l connected units are single vertices or hypergraph edges. L e t us formally define hyper-D-width. L e t H = (V, E) be hypergraph. A hyper-D-decomposition of a H is a pair where T is a tree a n d W = {W \t  (T,W)  € V ( T ) } is a family of subsets of  t  V(H)  such that for every connected set e G E(H): (HI)  T\ := {t\W n e ^ 0} ^ 0, a n d e  t  (H2) T h e s u b g r a p h of T w i t h vertex set T\ a n d edges {(s,t)\W e  s  fl^nefU}  forms a connected subtree of T. T h e w i d t h of a hyper-D-decomposition (T, W) is the m a x i m u m of \X{\ — 1 over a l l nodes i € T.  T h e hyper-D-width of a hypergraph is the m i n i m u m w i d t h  over a l l its hyper-D-decompositions. Hyper-D-width is useful for solving several h a r d problems. I n particular, we w i l l show, i n C h a p t e r 5, how we c a n find polynomial-time a p p r o x i m a t i o n schemes ( P T A S ) for vertex cover, d o m i n a t i n g set, a n d m u l t i c u t problems o n hypergraphs when.the hyper-D-width of the i n p u t hypergraph is constant. \<  ~ '  14  N e x t , for the purpose of computability, we introduce another measure, called hyper-T-width, w h i c h is slightly different from hyper-D-width, inherits almost a l l algorithmic and s t r u c t u r a l properties of hyper-D-width, a n d , i n contrast t o hyperD-width, is computable when hyper-T-width is constant.  1.6  Organization  In C h a p t e r 2 we go t h r o u g h the details of our results o n e m b e d d i n g series parallel graphs into l\ w i t h d i s t o r t i o n 6.0. I n C h a p t e r 3 we talk about e m b e d d i n g between line metrics a n d discuss the usage of /c-separable permutations i n e m b e d d i n g b e tween fixed line metrics and i n other applications. W e then move our attention t o tree-width o n digraphs and hypergraphs. I n C h a p t e r 4 we review existing results o n generalization of tree-width On digraphs. I n p a r t i c u l a r , we study D-width a n d characterize the class of digraphs w i t h D-width one. W e also compare D-width w i t h several other parameters defined o n digraphs. N e x t , we generalize tree-width t o hypergraphs i n C h a p t e r 5 and compare our definition, hyper-D-width, w i t h other existing connectivity measures o n hypergraphs.  W e also find several algorithmic  applications of hyper-D-width. W e finally introduce hyper-T-width w h i c h is slightly different f r o m hyper-D-width and has the advantage that it is computable i n p o l y n o m i a l t i m e when hyper-T-width is constant.  15  Chapter 2 r,  i\ embedding of series-parallel graphs 2.1  Introduction  T h e £\ metric e m b e d d i n g is of particular interest for its connection t o the sparsest cut p r o b l e m w h i c h , i n t u r n , is the m a i n ingredient of various algorithms that have a - d i v i d e ' a n d conquer nature [28]. A s outlined i n Section 1.2.1, t h e sparsest cut p r o b l e m c a n be interpreted as a m i n i m i z a t i o n problem over t\ metrics.  One can  solve the p r o b l e m as a m i n i m i z a t i o n over a l l shortest p a t h metrics defined o n the "underlying g r a p h , by linear p r o g r a m m i n g , and then embed the solution into l\. T h e d i s t o r t i o n i n c u r r e d b y the embedding is essentially the same as t h e a p p r o x i m a t i o n factor. In fact, i f for any edge weights o n a graph G, we can embed the corresponding metric into t\ w i t h d i s t o r t i o n c then the sparsest cut could be approximated o n G w i t h factor c. W h i l e every metric is embeddable into t\ w i t h d i s t o r t i o n O ( l o g n ) [13] a n d the b o u n d is realized by g r a p h metrics for expander graphs [39], for special classes 16  of metrics better bounds exist. G r a p h metrics for trees and outerplanar graphs are isometrically embeddable into t\ [41]. I n fact, a shortest p a t h metric corresponding to a g r a p h G is isometrically embeddable into i\ if and only if G exclude  as a  m i n o r [28]. Series-parallel graphs [28] and fc-outerplanar graphs [19] (for constant k) are embeddable into l\ w i t h constant distortion. P l a n a r graphs and b o u n d e d treew i d t h graphs are two widely know classes that are conjectured t o be embeddable into l\ w i t h constant distortion. R a o [43] proves d i s t o r t i o n 0(r y/log n) for any 3  m i n o r free class of graphs. T h i s yields d i s t o r t i o n  K  r%r  0(\J\ogn) for planar graphs a n d  b o u n d e d tree-width graphs. In this chapter, we prove a n upper b o u n d of 6.0 o n the d i s t o r t i o n of e m b e d d i n g series-parallel graphs into t\.  W e also prove a lower b o u n d of 3.0 for the  e m b e d d i n g a l g o r i t h m given by G u p t a et al. [28] even when the i n p u t metric is isom e t r i c a l l y embeddable into l\.  2.2 : Constructing the embedding In this section, we outline the m e t h o d that G u p t a et al. [28] use to o b t a i n a constantd i s t o r t i o n e m b e d d i n g of series-parallel graphs into l\. Series-parallel graphs are often defined i n a recursive fashion: A n edge  (s,t)  is a series-parallel graph w i t h terminals s and t. If G\ (resp. G 2 ) is a series-parallel graph, w i t h terminals  s\ and  £1 (resp.  s and 2  £2) then a  a new series-parallel g r a p h , w i t h terminals s\ a n d t , 2  and G  2  and u n i f y i n g t\ w i t h s . 2  series construction creates b y t a k i n g the u n i o n of G i  A parallel construction creates a new series-parallel  g r a p h , w i t h terminals s\ a n d t\, by t a k i n g the u n i o n of G\ and G , and u n i f y i n g si 2  with s  2  a n d t\ w i t h t 2  A n alternative way of constructing series-parallel graphs is more incremental.  17  We start w i t h an edge. A t each step, we choose an existing edge (s,t), introduce a new vertex x, a n d connect it to b o t h s and t by edges (x, s) and (x,t). A t the end of the construction, we may remove any subset of edges. T h i s actually constructs all tree-width-2 graphs, w h i c h are more general .than series-parallel graphs. A l s o we may assume that n o edges are removed at the end of the construction since we may choose the weight of every removed edge t o be infinity. G u p t a et a l . use this incremental construction t o define an ^ - e m b e d d i n g of the g r a p h , w h i c h is the e m b e d d i n g that we analyze i n this section. Consequently, all the results i n this section apply to tree-width-2 graphs. G u p t a et al.[28] present two fundamentally different methods for embedding series-parallel graphs into. t\ w i t h constant distortion. T h e first one, w h i c h yields a d i s t o r t i o n factor at most 13.92, recursively computes an ^ - e m b e d d i n g as a s u m of cut-metrics (See the definition i n Section 1.2.1).  T h e i r second approach is t o  represent series-parallel graphs as a probabilistic s u m of trees and bundles (special series-parallel graphs i n w h i c h all paths between the two terminals have the same length) w i t h d i s t o r t i o n at most 8. U s i n g the fact that trees are isometrically e m beddable into l\ and bundles are ^i-embeddable. w i t h d i s t o r t i o n at most 2, they conclude w i t h an ^ - e m b e d d i n g w i t h distortion at most 16. We focus on their first approach. T h e y use the incremental construction of series-parallel graphs to compute the ^i-embedding as follows: Let fi(x, y) be the shortest p a t h distance between two vertices x and y and  jl(x,y) be the £i-distance to be computed. Initially, when the construction.starts w i t h a single edge (s, t) we set Ji(s, t) = /j,(s, t). A s s u m e that i n one step we introduce one vertex x and attach it to the endpoints of an existing edge (s,.t). L e t  6=  fi(x,s) + fj,(x,t) - n(s,t) 2  and 18  Ps =  n(x,t) - n{x,s) + fj,(s,t) 2/x(s,t)  a n d for every existing vertex y let  ji(x,y)=6  + P p,(s,y) + (l-P )ii(t,y). a  a  (2.1)  F i r s t , fi is isometrically embeddable into l\ since it is the s u m of a cut metric a n d two isometrically embeddable metrics. N e x t , to show that /} has low distortion, it is easy t o verify that ft, preserves edge lengths, i.e., for every edge (x,y) € G,  p,(x,y) = n(x,y). that  However i f  x and y are not adjacent i n G, we need t o show  p.(x,y) > ii[x,y)/c to prove that the distortion is at most c. T h e fact that  P{x, y) ^ M^j v) follows f r o m \i being a shortest p a t h metric and f r o m every edge length being preserved i n the new distance. T o show that  p,(x,y) > fx(x,y)/c, G u p t a et al. consider two cases based o n  the ancestor relation between x and y. T h e ancestor edges of vertex x are the parent  edge (s, t) t o w h i c h x is attached d u r i n g the incremental construction plus all the ancestor edges of s and t. T h e i r cases are:  Case 1: y lies on a n ancestor edge of x . Case. 2: Neither x nor y lies on an ancestor edge of the other. For case 1, w h i c h turns.out t o determine the distortion of the embedding, G u p t a et al. use a n inductive argument to prove that  •..  ,,  •A(x,y)> "f^" M(x,y) (1  1)  for all-f'€ {\, 1). In p a r t i c u l a r , for £ = \/3 — 1 this gives the best b o u n d ( ^ K ^ 2  1^02-  - 1  ) ~  W e show that the worst distortion i n case 1 occurs when the sequence of  ancestor edges f r o m x t o y has a special degenerate f o r m ( L e m m a 3). U s i n g this 1  fact and the proof technique of G u p t a et al., we can show that the d i s t o r t i o n of p, is at most 9.0. However, i n order to o b t a i n our result, that the d i s t o r t i o n of jl is at 19  F i g u r e 2.1: T h e g r a p h  G > for e = ( s , i ) . x  e  6  6  most 6.0, we need a more precise inductive argument t h a n the one used by G u p t a et a l . T h i s argument appears i n L e m m a 4. We also show, i n section 2.6, that the a l g o r i t h m of G u p t a et al. produces a n l\ metric jj, w i t h d i s t o r t i o n at least 3.0 o n a family of outer-planar graph metrics; metrics that are k n o w n t o be isometrically embeddable into l\.  2.3  Flattening  For a vertex  x a n d an ancestor edge e = (s,t) of x, let ( ( s i , £ i ) ,  (s2,t2)> • • • >  (sk,tk) =  (s,t)) be the sequence of ancestor edges of x f r o m x t o (s,t). T h a t is, (si,ti) is the parent edge of either s$_i or ti-\  depending o n whether U — £j_i or Si = S j _ i  respectively. T o s i m p l i f y our definitions, we assume SQ = x and to — h- Note that for every 1 < i < k either £j = ti-i of  G that contains x a n d  {SJ,£J|1  or Sj = Si-\. <  Let G '  x e  be the induced subgraph  i < k}. T h e graph G ' is a sequence of edgex e  weighted triangles. L e t L j =  = /i(sj_i,Si), and  = / i ( ^ _ i , t j ) . See  F i g u r e 2.1. It is i m p o r t a n t t o note that the shortest p a t h between any two vertices in G  x,e  is the same as the shortest p a t h between those two vertices i n G. A l s o , the  definition of jl o n the (series-parallel) graph G  x,e  g r a p h G restricted t o the vertices i n G ' , x e  is the same as p, o n the, original  as long as the order of construction used  i n the two definitions is the same. 20  F i g u r e 2.2: F l a t t e n i n g a triangle. T h e right figure is really two degenerate triangles. A triangle w i t h edge lengths a, 6, a n d c is The  flat i f a = b + c or a = \b — c|.  flattened version, F ' , of G ' contains two flat triangles for every triangle i n x e  x e  G ' . If Si ^ Si-\ (and £j = £j_i) then  contains the flat triangles  x e  and  (si,Ui,ti) where i i j is a new vertex not i n G a n d  Ai(ui,£j_i) = ' L  + Z  " " 2  ^(si,Ui) = ' ~ ~ ' L  1  2  L  , a n d fj.(si}ti)  contains the flat triangles (£i_i, in G and  =  n(ti,Vi) =  Uj) =  L  '~  L l  2  ~  1 + Q  ',  ' , Ai(si-i,£i-i) = i i - i ,  1 + a  + a i  /X(SJ_I,  itj, £j_i)  (SJ_I,  L  i  ~  L  = Li. If £,; ^ £j_i (and Sj = S j _ i ) then F ' 1  6  Vi, s , _ i ) a n d (ti,Vi,Si) where i>j is a new vertex not  ^ \  MK^-I)  = ^±%i±^,  ,(s -. ,t -\)  v  i  x  i  = ^t-i,  a n d n{si,ti) = Li. For example, see Figure 2.2.  ;  T h e graph F ' is series-parallel a n d it defines the same graph metric o n the 1  vertices of G  x,e  6  as the graph G does. T h a t is, the shortest p a t h distance between  any two vertices i n G  x,e  remains unchanged i n F ' . x e  W e m a y also construct  F  x,e  following the order induced b y the construction order of. G w i t h Ui added after S ; and before  (and vi added between U a n d £i_i). U s i n g this construction order,  let ftp be the l\ distance obtained b y G u p t a et al.'s construction (definition (2.1))  on F > . W e first prove that jlp(x,y) < ji(x,y). x  e  21  Lemma 3. For an endpoint y of an ancestor edge e of x, P-F(X,V) < P(x,y).  Proof. W e prove, by i n d u c t i o n of the order of a d d i t i o n of the vertices, that PF{W, y) < p\(w,y) for every vertex w i n G > . If w is an endpoint of e t h e n p,p(w,y) = x  e  jl(w,y) = fi(w,y). Otherwise, assume :w — s.;_i a n d  Sj_i /  Si  (the case  w = U-i is  similar). A c c o r d i n g to the i n d u c t i o n hypothesis, jlp(si,y) < jl(si,y) and jJ. {~ki>y) < F  p,(ti, y). L e t a = L j _ i , b — Li, a n d c = a^. B y definition (2.1) of ftp, for p^ = ^ a  i2 {si-i,y) F  = 0+p pF(ui,y) F  =  + (1  b  a  + c  -PF)PF{U,V)  ^ - — ? r ^ ~ + pF(si,y^j  + (1 ^ PF)pF(ti,y)  .  B y definition (2.1) of / i , for p =  —-+pjl(s ,y) + (1 - p)jl{ti,y)  jj.(si-i,y) =  l  Hence,  AF(S»-I,J/) -  p(si-i,y)  < (pF-p){P{si,y) < b\p -p\ F  _  (a —  ~  -  - (1 (1-PF)^~—-  b + c)(b — a + c) 2(a + 6 + c)  ~ P F ) ^ | — -  (a — 6 + c)(b — a + c)  2(a + b + c)  = 0  • 22  ,  A s G u p t a et a l . mention [28], we can view the c o n s t r u c t i o n of fi as a p r o b a bilistic process. If we are at a vertex x w i t h parent edge (s,t), we accumulate <5 (for the triangle (x,s,t)) a n d then collapse (move) to either vertex s w i t h p r o b a b i l i t y P  s  or to vertex £ w i t h p r o b a b i l i t y 1 — P . B y repeating this process, we move f r o m x t o s  the edge (sk,tk) a n d accumulate 8 for some triangles i n the sequence. L e t P be the s  l  p r o b a b i l i t y that when x moves to the edge (si,U) it moves to Sj a n d let PI = 1 — P s. l  T h e expected s u m of the accumulated <5's plus P^L^ (resp. Pj°Lk) is fi(x, y) if y = tk (resp. y = s ). k  Define A to be the expected s u m of the <5's accumulated over a l l 1  triangles u p t o the edge (si,tj). So, for example, A = 0. L e t A = A .  and  p.(x, t ) = A + P*L k  k  Then  k  0  jl{x, s ) = A + k  P L. k  t  k  A s a corollary of L e m m a 3, we have  Corollary 1. For an endpoint y of an ancestor edge e of x, A F ( Z , y) + A  F  < fi{x, y) + A  where A (resp. Ap) is the expected total of S's over all triangles through which x is collapsed to y in G  x,e  (resp.  F ). x,e  Proof. L e t e = (w,y) a n d L = /j,(w,y). A s s u m e when x collapses to e i n G ' (resp. x e  F') x e  qG  it collapses to vertex y w i t h p r o b a b i l i t y pa (resp. pp) a n d to w w i t h p r o b a b i l i t y  (resp. qp). A c c o r d i n g t o L e m m a 3, jj,p(x,y) < jl(x,y) a n d p,p(x,w) < fi(x,w).  Hence Ap+qpL = fip(x,y) < fi(x,y) = A+qcL. Hence  Similarly, Ap+ppL  jl(x, w) = A +  PGL.  < A + min{Qc — q ,pG  PG,PG ~ PF} <  A . Consequently, p,p(x,y) + Ap < jj,(x, y) + A .  F  23  —  PF}  = jlp(x,w) <  = A + mm{pp — •  Distortion 9.0  2.4  In this section we show how the flattening l e m m a ( L e m m a 3) enables us t o use G u p t a et al.'s proof, w i t h m i n o r changes, to get a d i s t o r t i o n 9.0 b o u n d for series-parallel graphs. T h e y prove the following three inequalities for any £ G (5,1). (a) If  Pi~ > £ then fj,(x, Sj) > £L(X, S i _ i ) + (2f - 1)^.  (b) If  Pt >  l  l  ( then p{x, )  > A(s,ti_i) + (2£ - l ) L i -  Si  (c) Otherwise, 1 - £ < P ] "  1  < £ a n d p,(x, s ) + ^ ( A *  - A  t  i _ 1  ) > p,(x, Si-i) + a*.  T h e above three inequalities i m p l y  P(x, ) Si  + Y3^(  A i  - ' A  _ 1  )  ^ min{/i(x-,s _i) + (2£ - 1 ) ^ , ^ , ^ - 1 ) i  + (2£ - l ) L i } (2.2)  T h e left h a n d side of the inequality, when accumulated over all values of i, generates a value not more t h a n (1 + -^)p(x,  s^). T h e right h a n d side is a (2£ — 1) factor  of some p a t h f r o m x t o Sfc. ( A t step i we choose either t h e edge w i t h length c*i or the one w i t h length Li depending o n the m i n i m i z i n g argument.) Hence, jl(x,Sk) at least a factor (2f - 1)/1 +  =  0  f f.i(x, s ). k  is  C h o o s i n g £ = \/3 - 1 t o  m a x i m i z e this factor gives a d i s t o r t i o n b o u n d of at most 13.92. G i v e n flattened triangles, we can improve inequality (2.2) and o b t a i n a better  24  .distortion b o u n d . If a triangle is decreasing, i.e. L j = L j _ i — CVJ,  A(x, Si) = A* + PJLi  = A = A  i _ 1  i  _  1  +P*" ^ + P J " ^ 1  1  + P t \ U  +  Q i  /i(a;,Si-i) + ( i ^ -  =  Similarly, /}(£, Sj) = / t ( x , £ i _ i ) + ( P /  - 1  1  )  + (Pi-  -  1  - P r  ) a  1  Pt )*i l  i  — P * ) L j . F o r a decreasing triangle, P _ 1  s  = 1  i n E q u a t i o n (2.1). T h u s , the p r o b a b i l i t y of a move from S j _ i t o £j is 0, w h i c h means and A* - A  Pi = pi-  1  (a) i f P t  1  i  _  1  = P ^ W Thus,  > | then ji(x, s ) = / i f o t i - i ) + ( P p - P't^U 1  {  (b) o t h e r w i s e , P  t  i _ 1  < § a n d p.(x,Si)  + 2(A  i  + (3P*" - P r ) " * >  jl(x,  1  -  A  i _ 1  )  =  > jl(x,Si)  + + 2P ~ ai l  l  s  >  *-I) +f .  1  Together, these inequalities i m p l y ft(x,  )  Si  + 2(A*  - A*" ) > m i n 1  S i  If the triangle is increasing, i.e. L j =  _ i ) + j , fc(x, t^)  +y } •  (2-3)  + a , , then /i(x, si) = p.(x, Si) + ai, w h i c h  again implies inequality (2.3). U s i n g inequality (2.3) i n place of (2.2) i n G u p t a et al.'s proof gives us d i s t o r t i o n at most 9.0.  2.5  Distortion 6.0  T h e inductive construction of the graph and equation (2.1) encourage us t o express fl(si-i,y)  i n terms of fi,(si,y)  and jj,(ti,y),  and t o reverse the direction of i n d u c t i o n  used i n G u p t a et al.'s proof. A l s o , where the above approach derives a n inequality based o n a single vertex Sj (or, symmetrically, i j ) , we find that a parameterized 25  s  u X*  F i g u r e 2.3: A pair of flattened triangles i n a triangle sequence f r o m x to an ancestor edge w i t h endpoint y. C o n s i d e r i n g this case provides some i n t u i t i o n for our stronger, parameterized, inequality. inequality based o n an average of p,(si,y) and  y) leads to a better d i s t o r t i o n  b o u n d . T h e price we pay for using this stronger inequality is a much more c o m plicated inductive step. mathematics.  In fact, the details of the proof are five pages of dense  In this section, we give some i n t u i t i o n for the result b u t leave the  details to Section 2.8. R a t h e r t h a n a single flat triangle, consider the pair of triangles i n F i g . 2.3. For that triangle pair,  p(u, y) = pp,(v, y) + (1 - p)p.(t, y) = p/2(s, y) + (1 - p)ft{t, y) + prf and H(u, y) = m i n { ^ ( s , y) + a + 7, n(t, y) + L + 7 where p=  a}  •  A n y d i s t o r t i o n inequality of the form  fj,(u, y) > c[i(u, y) translates, using the  above equations, into an inequality that has c o n t r i b u t i o n from b o t h s and t:  pp(s,y) + (1 -p)ji(t,y) +pj> cmm{/j,(s,y) + a + j,p,(t,y) + L + 7 -  26  a}.  B y replacing a w i t h the equivalent (1 — p)(L + 7) a n d m o v i n g p*y t o the right we obtain: >cmin{  pp(s,y) + (l-p)p(t,y)  fj,(s, y) + (1 - p)L + (2 - p - p/c)j, n(t,y)+ L-py(l-l/c)} P  - W h e n we include a A t e r m on the left, this is very similar t o the inequality 1  (2.2) used b y G u p t a et al. Notice that we can view 7 as a parameter a n d o b t a i n all flattened triangle pairs. T h e d i s t o r t i o n 6.0 result is based o n inequality (2.4) setting c = | , using A  by  w i t h coefficient one o n the left side a n d replacing 27 w i t h  1  (3. W e also a d d 2/3 m i n { P , P } L j t o the right side to make the i n d u c t i o n work. s  l  t  l  L e t p\ — p,(si,y) a n d fi\ = /z(sj,y) for all i (p\ a n d [x\ are defined similarly).. L e t A j = A — A , i.e., A j is the expected s u m of the 5's accumulated over all triangles 1  s t a r t i n g f r o m the edge  (si,U) u p to (sk,tk).  T h e precise form our i n t u i t i o n takes is  ¥ ((3) = l / 3 m i n { / 4 + P\U.+ (3{l - 2P*), £ + PIU - PJ0} + 2/3 m i n { i » s  PfiLu  and  & (J3) = l / 3 m i n K + t  P\U  - P/./3, j + P\U M  + (3(1 - 2P})} + 2 / 3 m i n { P ; ,  P\}U.  Lemma 4. Forflattenedtriangle sequences, for all 0 .< i < k and all (3 > 0,  Proof. See Section 2.8.  •  L e t us derive the corollary that is used i n proving that p.. has d i s t o r t i o n at most 6.0.  27  Corollary 2. Forflattenedtriangle sequences from x to an endpoint y of an ancestor edge of x,  Proof. Since P ° = 1, A = A n , and /i° + LQ •P°£° + P ° £ ° + A  0  > JJP = s  fi(x, y), we have  = £ ( * , y) + A > ¥ ° ( 0 ) = vr,°( ) > 0  T h e following theorem shows that G u p t a et al.'s construction produces a n ^i-embedding w i t h d i s t o r t i o n at most 6.0.  Theorem 1. For any two vertices x and y, ji(x,y) > Proof. W e have two cases. Case 1: y lies o n an ancestor edge of x. In this case, by L e m m a 3 and C o r o l l a r y 2, A  F  2fi(x, y) > 2p,p(x, y) > fi (x, y) + F  w h i c h yields a d i s t o r t i o n of 6.0.  >  Case 2: neither x nor y lies on an ancestor edge of the other. T h e proof of this case is essentially the same as i n G u p t a et al. [28]. If x a n d y are n o t ancestors of each other then let (s,t)  be the last edge  added i n the construction that is a n ancestor edge of x and a n ancestor edge of y. If (s,t) separates x and y (i.e. every p a t h f r o m x to y passes t h r o u g h s or t) then p,(x,y) = A  x  where A  x  (resp. A ) y  + AV + (P?P? +  P*PV)L  is the expected s u m of the <5's accumulated over all triangles  s t a r t i n g f r o m x (resp. y) t o the edge (s,t), P  x  28  (resp. Ps) is the p r o b a b i l i t y that  x (resp. y) collapses to s when it moves to (s,t) (similarly for P  x  L = n(s, t). W e know P P? + P P X  generality, suppose P  x  a n d P?), a n d  > ± m i n { P f + P j , P * + P "}. W i t h o u t loss of  y  t  + P | = m i n { P f + P j , P f + P }. So,  x  7  t  y  jl(x, y) = A + A + (PfP? + IfPV)L x  y  x  + A -\-  px  > A  y  i  pV  L  s  2 =  A  a  + /i(a,t) 2  >  A ^ + A(y,£) 2 rix,t) (y t) +li  -  6  Corollaries 1 a n d 2  t  6  J  '  If (s, £) doesn't separate x a n d y then there must be a vertex q whose parent edge is (s,t)  w i t h (s, q) an ancestor edge of x and ( i , 5 ) an ancestor edge of y. T h i s  case reduces to the previous case by noting that fi,(x, y) is preserved by reordering the construction sequence i n such a way that (s, q) becomes a c o m m o n ancestor edge of x a n d y. (See G u p t a et a l . [28] for details.) Consequently, the d i s t o r t i o n is at most 6.0.  2.6  •  Lower bound  T h e r e are series-parallel graphs that cannot be embedded into t\  w i t h o u t some  distortion. T h e best lower b o u n d o n this distortion, of w h i c h we are aware, is 3/2 and is obtained by showing that any ^i-embedding of the unweighted bipartite graph K2,n (which is series-parallel) has d i s t o r t i o n at least 3/2 [4]. If we restrict our embeddings to be those produced by G u p t a et al.'s construction, we c a n prove a better lower b o u n d . T h e following theorem shows that there exist outerplanar graphs whose t\ embedding v i a that construction incurs dis-  29  Vn-1  Figure 2.4: Lower b o u n d example t o r t i o n a r b i t r a r i l y close to 3.0, even t h o u g h outerplanar metrics are isometrically embeddable into £\.  Theorem 2. There exists a family of outer-planar graphs whose l\ embedding, by the construction of Gupta et ai, has distortion arbitrarily close to 3.0. Proof. L e t G be defined as follows. V{G) = {xi : 0 < i < n}u{yi : 1 < i < n—1} and  E(G) = {(xi, x i) of length 1 : 0 < i < n - 1} U {(xi,y i) i+  i+  of length 1 : 0 < i  <  n - 2} U {(xi, yi-i) of length 1 : 2 < i < n} U {(xi,yi) of length 2 : 1 < i < n - 1}. See F i g . 2.6. E v e r y shortest p a t h i n G from xo to x  n  has length n. A s s u m e that the first  edge added i n the incremental construction is (XQ,XI). T h e construction order of vertices is fixed once this first edge is added; they are added i n increasing order of their index, i.e. (XQ,X\),  y\, X2,  to  y2, • •• •  =  L e t t i n g /Ttj = fi,(xi,xo), we have  A n - i + fhi-2 + 1 ' o —  30  where po = 0 a n d pi = 1. L e t g, = pt - §, then n  + 2  9n-l 9n  =  9n-2  where go = 0 a n d g i = | . T h i s implies that 0 < g  n  f  <  M  n  <  < 2/3 for a l l n, w h i c h means  + 2 / 3 o r equivalently  f  A s n increases, we o b t a i n d i s t o r t i o n a r b i t r a r i l y close to 3.0. If the order of incremental construction starts w i t h the edge (XJ,V) for v G {XJ I,yj+i,Uj-i,  Vj}, then either j < n/2 or j > n/2 a n d the same argument, w i t h  pi — p(xj,Xj i)  or pi = p(xj,Xj-i),  +  +  respectively, gives d i s t o r t i o n approaching 3.0  •  as n approaches infinity.  2.7  Conclusion and Future Work  In this chapter we provided a careful analysis of G u p t a et al.'s construction a n d obtained a n upper b o u n d of 6.0 a n d a lower b o u n d of 3.0 o n the d i s t o r t i o n of e m b e d d i n g series-parallel graphs into l\ using that construction. One might also consider the p r o b l e m of m i n i m i z i n g the dimension of the l\ metric as well as its distortion. B r i n k m a n a n d C h a r i k a r [14] show that embedding certain series-parallel graphs (diamond graphs) into l\ w i t h constant d i s t o r t i o n requires n ^ ) dimensions. W h e t h e r low dimensional, constant d i s t o r t i o n embeddings 1  for a l l series-parallel graphs c a n be constructed efficiently is a n open p r o b l e m . A very challenging problem is to embed bounded tree-width graphs into £\ w i t h low d i s t o r t i o n a n d , as a first step, graphs w i t h tree-width 3.  31  2.8  Proof of Lemma 4  For flattened triangle sequences, for a l l 0 < i < k a n d a l l (3 > 0, P ^  +^  + Ai>max{^ (/3),^(/?)}  (2.4)  s  Proof, (of L e m m a 4) T h e proof is b y i n d u c t i o n . We-assume t h e l e m m a is true for i, i + 1 , . . •, k a n d show it is true for i — 1. W e know Aj Aj-i  = < pi  . a i  when L j = L j _ i + CVJ or L j = L j _ i + /3j + Aj  ^P/A + A j  w h e n L j = L j _ i - a,  u  when U = U-  - for  X  Since inequality (2.4) is s y m m e t r i c i n Sj and t j , we m a y assume w i t h o u t loss of generality, that £j = £j_i w h i c h means :  collapses t o  Sj_i  (SJ,£J).  " T h e proof relies o n four technical lemmas (Lemmas 5, 6, 7, a n d 8).  Case 1: (increasing triangle) L j = L j _ + ai'. x  Notice that i n this case A j = A j _ i and PIs -= *Ps  Li  Li  Li  piiii+piti+Ai (by the i n d u c t i o n hypothesis)  > ^l(P) > *r (^) :  W e also need to show that P  1  '  1  ^  32  (by L e m m a 5).  +P^ti'  1  + i - i > ^j A  - 1  ^)-  UP}'  1  all /?.>  0.  > \ or ^ - + P - L ^ l  l  i  I n this case  P J  -  ^ -  1  i 1  l  l  1  s  +^ T ^  1  then  < f.L - +P - L ^  l  -  1  +  i  l  _ 1  *s (0) = *t (0) > _1  >  i - i  A  < * t ( 0 ) for _1  *t (0) _1  for a l l 8 > 0 a n d we are done. . Otherwise, P * " < ± a n d / 4 " + P J 1  1  _ 1  Li_i >  +PT^i-i-  Define ^  _  M s ~  M t +  T h i s is the value of / 3 that maximizes m i n of ^\(8)  - P s ) ^  ^  0 since  P * _ i >  r  p} ~ + P^  1  l  s  = £ + PtU + B {\ - 2PI) %  L^i  > /Jf  1  +  P  i s  _  1  X  l  _ i .  A l s o note that Bi  since (^ + p * L ) - ( j + p L . ) i  M  s  i  i  Hence •  p r v r  1  + v r  5 )  ( / 3 ) b y m a k i n g the two values i n the first  equal, i.e., /4 + P\U - PiBi  N o t e that  (-Pt ~  1  + * - i = «  +  A  ^  + A*  >max{*j(jBi),*i(0)} >  * j  _  1  ( P i _ i )  33  ( b y  ( b y induction) L e m m a 6)  > 0,  Case 2 : (decreasing triangle) L = L j _ i — a.;. t  In this case P = P S L _ 1 , / i * , l  s  p r v r  1  + ^ r ^ r  - 1  = ji\ + O j ,  + ^ - i  1  = /i* +  and A j _ i = A j + P^a;, so  = PM+<*)+piti  +  + Ai + 2 P > i  = pi&  + piti  >  + 2ai) + 2 P a s  - 1  - 1  i  (by i n d u c t i o n )  i  (by L e m m a 7).  > %^(P) We also need t o show that P * / ^  ^  + P/ /^ - 1  - 1  + i - i ^ ^t^G )A  9  I  n  t h i s  case, p r v r  1  + p t t i ~ + A i _ i =P l  X  l  +  t  _ 1  5  v  0}) + 2 P ; a i  > ¥ (mzx{Bi, >*j  A , + 2 P  +  (Pi_i)  (by i n d u c t i o n )  (by L e m m a 8)  Base Case T h e only r e m a i n i n g step is t o prove the base case. H = k  8  = L  and ^ = / i * = 0. T h u s , P jl k  k  + Pftf  k  k  +  2/3mm{P ,P }L k  k  < l/3P L k  k  =  k  +  2/3P L k  k  P Lkk  34  k  + A  *£(/?) = 1 / 3 m i n { 4 + P / % + (3(1 - 2P ),rf A  Assume t  and  = PL k  k  k  + PU k  = y.  -  P (3) k  W e have  A s for the inequality P jJ. k  P  k t  > \ then we are done because P fi k  Otherwise, assume P *  t  fc  t  k  +P  = 1/3 ( P*L  L  fe  s  +  k  fc  2  P  + B (l i  2 p  -  k  +  "  ]  L  =^ L  f  c  and  2/3mm{P ,P }L k  k  k  )+  k  ) L f c  2/3P L k  k  s pk\2 P f  2L (P Dk _k  = P^L  P  > tf*(0) = # £ ( 0 ) p  k  k  as mentioned earlier, i f  ~ "  - 2P ))  k  n  k  =  k  fc  +A  k  t  < ±. It's clear that B  fc  ( P ) = 1/3  <  A  + P jl  k  ^t(P),  + fc >  + PtPt  k  k  k  3P  k  PsL  k  = Pp k  + P jl  k  k  + A  k  k  T h e proof is now complete.  •  Lemma 5. If Li = L j _ ! + oti then for all 8 > 0 :  *l(p)>V- (8). l  + a j , A j = A j _ i a n d P* = P,:-i s - •«• s  Proof. Notice that since L j =  ¥ (3) s  = 1/3min{/4 + P % + 8{l - 2P ), & + P L, l  t  +  :  '  -  L  - 1*8}  i  s  1  t  i  + P r ' ^ - i + ^(1 - 2Pi), M p + ^ T % - i 1  + 2/3min{PJ,P/}L  <  s  i  Li •  2/3mm{P ,P }L  > 1/3minK"  since  l  s  ii-  > 1/3 m i n K -  i  = ^"'t'^,  A4  1  +i T  1  *i =  )  and P j = P * "  ^ - ! + 0(1 - 2 P J - ) , M l 1  + 2/3nun{PJ- P/- }L _i 1  TO  1  i  35  - 1  1  ^  +* T ^.-i -^ r V }  since P*.< P * "  1  = *r (/?)i  •  • R e c a l l the definition of Bi from the equation 2.5.  Lemma 6. If Li = L j _ i +  and P j _ i > 0 then  m^{¥ (Bi)^\{0)}  >W -\Bi-ij  t  Proof  If Pi < 1/2 t h e n  *r (^_i) x  -  t  >tfj(O)a n d l  1  t  ' -1/3(AJ + PtLi = =  -  IAA;- +K~ Li-i+p -i(i  2Pr )+2/3^-^-1 x  + Bi(l- 2PD) - 2/ZPtLi  l/3P _ (l-2P/- )-l/3P (l-2P i  1  1  l/3P _ (2P;i  1  l  t  l  )-2/3a  - 1) - l / 3 P i ( 2 P i - 1) -  1  = i/a^-^ +  ^  i  ;  -  1  ^  -  1  i  2/3oi ^  -  !  )  Ps - l /  " ^  s  t  +  ^ '  P  :  )  L  ( 2 P ; - 1) - 2 / 3 ^  l  •* s  1  <  1/3^ -l/3^  i f pi—1-  ^  s  ^  1  pi—!'> s  '  *  1 ) L i  pi 1 +  1  P  t  ~ (2P]- -l) 1  x  - ( 2 P J - 1) - 2/3a* 1  .s  -2/3a* +l/3( r M  1  - MP  1  + {PI  1  PT^-iXi  ~  - T^r) s  <  -2/3a, + l/3(2Pr P. -i)( 1  pi—1 _ pi—1  <  0 36  t  p  i  Ps  _ '  )  P s  Otherwise, if P\ > 1/2 then * j ( 0 ) >  tr ^-!)-*^) 1  a  n  d  i/3(zir +pr ^-i+^_i(i-2Pr )+2/3Pr i  1  i  -l/3(AJ + P % ) - 2 / 3 P % s  s  i/3P _ (i-2P - )+2/3(pr -pr )^-i  =  i  t  1  i  1  i  1  = i/s^' - AT + (^r - ^r )^-! 1  1  1  1  (  2  P  i - i  _  1  }  Ps  +2/3(pr - p r ^ L i - i 1  i/3^-^(2Pr -i)+2/3(pr -pr )^  <  1  1  1  Ps  <  2/3Pr Li-i(2 1  -  -Jn)+2/3(p i  t  Ps  1  - pr )^-! 1  2/3  <  0  Lemma 7. 7/ L j = L j _ i — a j £/ien /or all B > 0 . r ( / 5 + 2aj) + 2 P > > v & r ^ ) 1  s  Proo/. L e t /?' = /3 + 2 a j . ' * (/3') + 2P a.j = 1/3 min{/4 + P / L , + J  s  s  - 2PJ),  l  ^  + P\L  %  - P^'} + 2/3min{P;, P/}L, + 2 P > . •  > 1/3 m i n K + PIU + S P ^ a , + p'(l - 2 P * ) ,  /4 + P J L j  +3P>j -  P 0} l  s  + 2/3min{P \ s  P^L^  (since 2 / 3 m i n { P , P ' } L ; + P * a ; = 2 / 3 m i n { P * , P } ( L i - i - a,) + P > ; > s  i  t  t  37  l  2 / 3 m i n { P , P / } L _ i + l/3P*«i > 2 / 3 m i n { F * , P ^ } L _ i ) s  i  i  i  =  1/3min{/xr  1  + PiU-x since /2*  + PiU-x - c*i(2 - 4P*) + P'(l + 2 i > i - Pi/3'} + 2 / 3 m i n { P \ 5  2PI), P^L^x  = fi\ + CUJ and L i = L j _ i —  - l/Sminiy-  +P r ^ i - i +  1  0(1 - 2^ ), _1  ^r +pr ^-! - ^r /?}+2/3 m i n ^ 1  since P* = P*  1  1  1  1  , p*- }^ 1  and U = £j_i  R e c a l l the definition of P j f r o m the equation 2.5. L e m m a 8. If Li = L j _ i — cxi, P  .  t  4  < 1/2, and Bi-\  > 0 £/ien  *j(max{0 B })>*r (5i-i)-2Pia .  .  1  )  i  i  Proo/. If P i > 0 then  %{Bi)  =  l/3(/4 + P / L ,  = 1/3 (V  - P/P,) + 2/3min{i* P } L , t  + P*L, -  s  = 1/3 (fi-  1  -  + ( P - Pi)Li^j t  l  + 2/3P % t  - ai + P / ( L i _ i -  - 1/3 ( ^ ( A C * - « i - M P +  J  2 / 3 ^ ( ^ - 1 - ^ )  38  1  + tf? - Pi)(Li-i  -  ai))  since  fj,  =  l s  ji\  1  — a j , L j = L j _ i — a j , and P  t  l  = P/  1  < 1/2  - 1/3^(1 + 4P< - § ( 1 + P ))  = n ' \ B ^ )  t  1  •2  = *r (Pj_ )-2P]a, + l/3aj(9P -4) + 2/3aj |1  >  1  s  tfj-^Bi-i)  If P i < 0 then  - 2P;aj  U <  /Li» +  l  .  P  (since P/ < 1/2).  4 + P\Li  l/3(/4 + P  and tfj(O) =  t  % ) + 2/3P/Lj.  Since P j - i > 0, P j can't be too negative. I n fact,  B  =  f4-j4 + {Pt-  pi)L  _  t  ^T - /xj1  1  p i  +  (pr - pr )^-! - 2pr aj 1  1  p  - s  -  1  1  i  i  s  2P}oi 2P\ai B y - > ~ pi  = Bi-i  * s  1  s  Thus, *K0) = l / 3 ( * + P ^ i ) M  + 2/3P % t  = * j ( P j ) + 1/3P/PJ  = ^-H^j-i) - l / 3 a , ( l  + 4 P ; - § ( 1 + P^) + 1/3P/Pj Pis 2  > ^ ( S i - i ) - l / 3 o i ( l + 4 J » - § ( 1 + Pi)) - 2 / 3 a  pi  = ^rH^i-i) - 2 P > j + l / 3 a j ( 9 P ; > WftBi-i)  '• - t /y  -/  —<• pj P <  - 4)  (since P < 1/2).  - 2P ai l  l  s  t  •  39  Chapter 3  Embedding between Line Metrics 3.1  Introduction  In this chapter, we focus o n c o m p u t i n g an o p t i m a l e m b e d d i n g between t w o fixed line metrics. A line metric is a set of points o n a real one-dimensional line w i t h the distance between any pair of points being their l\ distance (any t\. distance is equivalent for one-dimensional points). A s we mentioned earlier, K e n y o n et a l . [36] consider t h e p r o b l e m of o p t i m a l l y ; e m b e d d i n g one fixed line metric into another fixed one. T h e y propose a polynomial-time, d y n a m i c p r o g r a m m i n g based, a l g o r i t h m that computes the o p t i m a l e m b e d d i n g if the distortion is less than 3 + 2\/2. T o this a i m ; they show that any p e r m u t a t i o n that contains (3,1,4,2) (see F i g . 3.1) as a sub-permutation corresponds t o a n embedding w i t h d i s t o r t i o n at least 3 + 2\/2.  A l l permutations that d o  not contain a ( 3 , 1 , 4 , 2 ) sub-permutation have a nice structure that allows  finding  the o p t i m a l such p e r m u t a t i o n using d y n a m i c p r o g r a m m i n g i n p o l y n o m i a l time. It 40  is w o r t h mentioning that the p r o b l e m is recently proven to be N P - h a r d when the o p t i m a l d i s t o r t i o n is unrestricted. H a l l et al. [29] prove that if the o p t i m a l d i s t o r t i o n 5 is at least n , for some constant e, then the d i s t o r t i o n is not even approximable £  w i t h a factor <5 ', for any e', unless P = N P . 1-e  In this chapter, we extend the result of K e n y o n et al. [36] by considering a less restricted class of permutations called /c-separable permutations. In particular, we improve the threshold value on d i s t o r t i o n below w h i c h an o p t i m a l embedding can be found i n p o l y n o m i a l time f r o m 3 + 2 ^ 2 to 13.602. We also study several interesting problems related to permutations such as forbidden permutations, p a t t e r n m a t c h i n g , a n d stack sorting. We recently found that K e n y o n et al. (in an extension of their conference paper [36]) a n d C h a n d r a n et al. [17] have also extended the 2-separable result to /c-separable permutations. B y considering 9-separable permutations, they o b t a i n a p o l y n o m i a l t i m e d y n a m i c p r o g r a m m i n g solution that works i n those cases when the d i s t o r t i o n is less t h a n 5 + 2^/6  ~ 9.90.  We o b t a i n (independently) the same result and show that the same technique can be used, by considering larger values of k, to find o p t i m a l embeddings when the d i s t o r t i o n is less t h a n 13.602. We (as well as they) show that the technique does not work for d i s t o r t i o n greater t h a n 13.928 no matter how large k is chosen to be. T h e structure of this chapter is as follows. A f t e r i n t r o d u c i n g basic definitions, i n Section 3.2, we prove, i n Section 3.3, that the class of /c-separable permutations have a finite set of forbidden permutations.  T h e n , i n Section 3.4, we propose a  p o l y n o m i a l time algorithms for embedding between two fixed line metrics provided the o p t i m a l e m b e d d i n g p e r m u t a t i o n is /c-separable. We also s t u d y some algorithmic and non-algorithmic related results such as c o m p u t i n g separability. Sections 3.6 is  :  41  devoted t o the p r o b l e m of finding a /c-separable p e r m u t a t i o n i n a text p e r m u t a t i o n . W e propose a p o l y n o m i a l time d y n a m i c p r o g r a m m i n g a l g o r i t h m for t h e p r o b l e m . In Section 3.7, we interpret /c-separable p e r m u t a t i o n s i n terms of the way they are sortable using a queue.  F i n a l l y , i n Section 3.8, we address some open problems  related t o our work.  3.2  Preliminaries  N o t i c e that we can view any e m b e d d i n g as a m a p p i n g f r o m source points to destinat i o n points or, simply, as a p e r m u t a t i o n . A s s u m e t h e o p t i m a l e m b e d d i n g between U a n d V is the p e r m u t a t i o n TT. (vr(l),7r(2),-..  )7  W e specify a p e r m u t a t i o n IT w i t h t h e n o t a t i o n  r(n)).  P e r m u t a t i o n 7r of size n contains p e r m u t a t i o n TT^ of size k, if there exist n  indices  h < h < ••• < h  K {k) < Kn{lj)n  TTn  V  such that for a l l 1 <  I n this case, we refer to  ir^ as  is t h e unique p e r m u t a t i o n of size  a  i < j < k, iTk(i) < ^k(j)  sub-permutation of 7 r .  y —x  n  + 1 such that  In particular,  nfi' (i) < ^n' {j) y  iff  v  iff  7T (i + 1 - X) < 7T (j + 1 - X). n  n  A  nice interval I  in  ix  is either a singleton or is a set of at least two consecutive  numbers f r o m 1 t o n such that their m a p p i n g , v i a TT, is s t i l l a set of consecutive numbers. F o r example, the p e r m u t a t i o n ( 4 , 3 , 1 , 2 ) contains several nice intervals: [1,2], [3,4], [2,4] a n d [1,4]. If the interval [ l , n ] c a n be decomposed into a constant number of subintervals such that each sub-interval is m a p p e d , v i a TT, t o a sub-interval i n V and this p r o p e r t y recursively holds for a l l sub-intervals, then we c a n use d y n a m i c p r o g r a m m i n g and find the o p t i m a l embedding. M o r e formally, a n interval  I  is  k-separable,  w i t h respect t o ir, i f either it has at most k points or it c a n be p a r t i t i o n e d into 42  nice sub-intervals h,l2,  (1 < m < k) such that each Ii is /c-separable. TT is  • • • ,I  m  /c-separable iff the interval [ l , n ] is /c-separable w i t h respect to TT. T h e  separability  of TT is the m i n i m u m k > 1 such that TT is /c-separable. For example, the p e r m u t a t i o n TT = ( 2 , 4 , 3 , 6 , 5 , 1 ) is 3-separable. I\ = [1,3], I2 = [4,5], I 3 = [6], a n d it is clear that I\, I2, a n d I3 are 3-separable as well. E v e r y 3-separable p e r m u t a t i o n is 2-separable, since for any three nice subintervals that p a r t i t i o n a p e r m u t a t i o n , two m a y be merged t o f o r m a nice subinterval.  Therefore, we don't have any p e r m u t a t i o n w i t h separability 3. It's also  easy t o see that for k > 4, there exist permutations of size k w i t h separability k. These p e r m u t a t i o n could be interpreted i n a simpler way: they don't have any nice interval except the interval [1, k]. W e refer to these special /c-separable permutations as  non-separable p e r m u t a t i o n s . T h e d i s t o r t i o n i n c u r r e d by a p e r m u t a t i o n TT, denoted by  d(jr), is the m i n i -  m u m d i s t o r t i o n i n c u r r e d by e m b e d d i n g any two line metrics U a n d V v i a TT. F o r example, d(?r) for t h e p e r m u t a t i o n i n F i g . 3.1 equals 3 + 2\/2 a n d happens w h e n [a, b, c, x, y, z] = [1,-^/2,1,1,-^,1]-  A s we see later, T h e o r e m 5 states that d(7r)  equals the largest eigenvalue of a 0-1 m a t r i x corresponding to TT. C o r r e s p o n d i n g to every p e r m u t a t i o n TT of size n, there exist three p e r m u t a tions TT°, TT , a n d 7 r 1  i's, TT°(i)  _ 1  that are similar to TT a n d incur the same d i s t o r t i o n . F o r a l l  = n + 1 — 7r(i),  7r (7r( i)) = 1  ,  i, a n d 7r ('i) = n + 1 — vr (i). F o r example, -1  if TT = ( 2 , 4 , 1 , 3 ) , 7T° — 7T = ( 3 , 1 , 4 , 2 ) a n d 7 r 1  1  _ 1  = TT. T h r o u g h o u t this chapter, we  always assume that a p e r m u t a t i o n comes w i t h a l l its four s y m m e t r i c forms. F o r example, w h e n we say 2-separable permutations avoid TT = ( 2 , 4 , 1 , 3 ) we mean they avoid ( 3 , 1 , 4 , 2 ) as well. L e t Ll/j be the set of all non-separable permutations of size k. L e t d  k  43  be the  l  a  2  b  3  c  4  7T  F i g u r e 3.1: T h e 4-separable p e r m u t a t i o n ( 2 , 4 , 1 , 3 ) . m i n i m u m d i s t o r t i o n over a l l permutations i n life. F o r example, II4 = { ( 2 , 4 , 1 , 3 ) } , n  5  = { ( 2 , 4 , 1 , 5,3), (2, 5 , 3 , 1 , 4 ) , (3, 5 , 1 , 4 , 2 ) } , and i t ' s not h a r d t o see that d = 4  al*, — 3 + 2\/2. N o t e that b y ir € Tlfc we i m p l i c i t l y mean v r , ^ , ^ 0  1  - 1  € 11^ as well.  So, ( 3 , 1 , 5, 2, 4) is also i n II5.  3.3  Forbidden Permutations  O n e c o m m o n l y asked question regarding many p e r m u t a t i o n classes is whether they can be characterized b y a finite forbidden set of permutations or not. F o r e x a m ple, a p e r m u t a t i o n is 2-separable i f and only i f it contains neither ( 2 , 4 , 1 , 3 ) n o r (3,1,4,2)[12]. Interestingly one can generalize this statement for fc-separable permutations. Theorem 3.  [3] A permutation is k-separable if and only if  • For odd k, it doesn't contain any permutation in Hk+i-  •  For even k, it contains neither a permutation in Tlk+i  where  n  o  r  k+2-  n  n^m is the permutation of size 2m in which TT*(2i)2m — i and  7r*(2i — l)2m —  i + m. A l b e r t and A t k i n s o n [3] (See T h e o r e m 4 i n their paper) use the n o t i o n simple 44  •  '  for non-separable a n d call Tx\ an exceptional p e r m u t a t i o n . T h e y o b t a i n their result m  by using some results f r o m Schmerl and Trotter [49] on p a r t i a l l y ordered sets.  3.4  Embedding between two line metrics  In this section we prove the following theorem w h i c h is a generalization of K e n y o n et al.'s result. Theorem 4. For any two line metrics U and V and any k either the distortion of the optimal embedding between U and V is greater than d +i or there exists an k  0(n  )  5k+3  time algorithm for computing the optimal embedding. R e c a l l that dk+i is the m i n i m u m d i s t o r t i o n over all permutations i n Ilfc+i.  L e t 7r be the o p t i m a l embedding p e r m u t a t i o n . If 7r is not /u-separable then, according to T h e o r e m 3, ir contains either a p e r m u t a t i o n i n Tik+i or  7r£  + 2  (in case that A: is  even). d(nl ) +2  is increasing and one can easily see that d(nl ) 2  — 21.954 . 1  Since  dk+i < 7 + 4\/3, according to T h e o r e m 6, we conclude that d(ir) > dk+i- Otherwise, if 7r is fc-separable, an a l g o r i t h m for finding the o p t i m a l e m b e d d i n g follows.  3.4.1  Algorithm  If the o p t i m a l embedding ir is /c-separable then we can compute i t i n time 0 ( n by a d y n a m i c p r o g r a m m i n g approach. two sub-intervals I = {u{,Uj+i,  • • •  5 f c + 3  )  E v e r y sub-problem is a m a p p i n g between ,Ui  + r n  -i}  and J = {VJ,VJ+\, • • •  , ^  +  m  _ i }  we specify by the triple (i, j, m). Moreover, we need to know the mappings of the four b o u n d a r y points of b o t h intervals for c o m p u t i n g the d i s t o r t i o n . T h u s , each entry TX1  1  2  = (7,1,8,2,9,3,10,4,11,5,12,6).  2k + 2.yjk(k-  In fact, it's not had to prove that d(ir^ ) k  1) - 1.  45  =  that  i  h  k  i + m-l  F i g u r e 3.2: A l g o r i t h m . i n the d y n a m i c p r o g r a m m i n g table corresponds t o 7 variables (i, j, m, i\,  j i , 32) i n  w h i c h i and j are the start of b o t h sub-intervals, m is the length of sub-intervals, i\ = 7r(z), %2 = 7r(i + m — 1), j i = 7 r ( j ) , and 32 = TX~ {J + m — 1). (See F i g . 3.2.) 1  _ 1  A s s u m e I is p a r t i t i o n e d into at most k sub-intervals i i , I2, • • • ,I  k  each I  x  is m a p p e d to an interval i n J . T h e r e are 0 ^  I into I 's. x  T h e r e are at most k\ possibilities for J 's. x  m a p p i n g of I .) x  and J 's x  f c _ 1  such that  ) possibilities for p a r t i t i o n i n g (We assume that J  x  is the  W e also need t o know the m a p p i n g for each b o u n d a r y of  w h i c h has 0 ( n  4 f c _ 4  I 's x  ) possibilities. ( T h e m a p p i n g for four of the b o u n d a r y  points is already known.) Once we have fixed all the sub-intervals and the m a p p i n g for a l l b o u n d a r y points, we c a n compute the d i s t o r t i o n by using the d i s t o r t i o n corresponding t o every sub-interval as well as the expansion and inverse expansion corresponding t o single edges between boundaries of consecutive sub-intervals. I n t o t a l , we need t o consider 0(n ~ ) 5k  5  cases and it takes O ( n ) t o c o m p u t e the d i s t o r t i o n  for each case. Since o u r d y n a m i c p r o g r a m m i n g table has 0 ( n ) entries, the t o t a l 7  r u n n i n g t i m e w o u l d be 0 ( n  3.4.2  5 f c + 3  ).  Largest Eigenvalue  A s s u m e t h e d i s t o r t i o n corresponding t o a p e r m u t a t i o n ix of [ l , n ] is A. T h a t means that for any two line metrics of n points each, the d i s t o r t i o n using ix is at least A a n d  46  there exists a pair of line metrics whose distortion, using IT, is exactly A. In fact it is not h a r d t o see that the m a x i m u m expansion and inverse expansion i n embedding U to V happens for a pair of consecutive points, so we need t o care only about t h e m . F i n d i n g d(ir) corresponds to solving a set of linear equations. F o r example, for the p e r m u t a t i o n i n F i g . 3.1, the linear equations are as follows.  <  y+z  or equivalently AX  x +y +z  < y/Xb  x+y  < y/Xc  a+ b  < y/Xx  a+b+c  < y/Xy  b+ c  < yfXz  < y/~XX, where A is the adjacency m a t r i x corresponding t o IT  a n d X is [a, b, c, x, y, z] . T  In general, for a p e r m u t a t i o n IT of size.n that corresponds  to e m b e d d i n g between two line metrics of s i z e . n , A has 2 n — 2 rows and columns  where, for all 0 < i,j <n, A[i,j] = A[n + i,n + j] = 0 and A[i,n + j] — A[n + i,j] is one iff the interval [7r(i),7r(i + 1)] (or [7r(i  +~l),Tr(i)] if ir(i) > ir(i + 1)) contains  the interval [j, j + 1] and is zero otherwise. We can also assume that, by scaling edge weights i n U or V if necessary, the expansion and contraction b o t h equal y/X. T h u s , for any single edge i n U and V we write a n inequality t o make sure that its corresponding expansion does not exceed  Vx. Since we are interested i n m i n i m i z i n g A we better make the equality AX y/XX.  Therefore, VX is a n eigenvalue of A.  =  It is well know that ([30], C h a p t e r  •8.2.) the only eigenvalue whose corresponding eigenvector is positive is the largest  47  F i g u r e 3.3: Illustration of p e r m u t a t i o n 7T15. eigenvalue. T h u s , \/A is the largest eigenvalue of A. Theorem 5. Let A  n  value be A.  be the 0-1 matrix corresponding to TT and let its largest eigen-  Then, the distortion of TT is exactly A and is obtained when the edge 2  lengths are taken according to the eigenvector corresponding to A.  3.4.3  Bounding d  k  A l t h o u g h d is increasing i n k, it remains bounded. T h i s is somewhat d i s a p p o i n t i n g k  since i f i t was u n b o u n d e d we could imagine a n a l g o r i t h m that finds a n o p t i m a l e m b e d d i n g for any two line metrics, no matter how large the o p t i m a l d i s t o r t i o n is, whose r u n n i n g time is a function of the distortion. Theorem 6. For any value k there exists a non-separable permutation ir whose k  distortion is at most 7 + 4v 3/  Proof. L e t iTm be the p e r m u t a t i o n on [l,2n] where 7T2 (l) = 2, 7T2 (2n) = 2 n — 1, n  n  •7T2 (2z) = 2i + 2, and 7i"2n(2i + 1) = 2i — 1, for i = 1, 2, • • • , n — 1. Similarly, 7T2 +i n  n  is defined as follows. 7r2n+i W = 7T2?i W> for i — 1, 2, • • • , n — 1, 7T2 +i(2n) = 2n + 1, n  and 7r2n+i(2n + 1) = 2n — l(See F i g . 3.3). '  ' Set du(2i - l , 2 i )  = 1, d (2i,2i v  + 1) = \/3, d (2i v  - l , 2 i ) = 2 + \/3, and  dy(2i, 2i + 1) = 3 + 2\/3. T h e d i s t o r t i o n corresponding to this pair of point sets is 7 + 4\/3 w h i c h means d <7 k  + 4a/3 ~ 13.928. 48  J  k distortion  5  7  9  11  13  15  17  8.352  10.896  1-2.045  12.651  13.007  13.233  13.385  19 13.492  Table 3.1: D i s t o r t i o n of TT for several • values of k. K  12  fc  4  dk k  5.828  6 8.352  9.899  10.896  11.571  dk  13.131  13.316  13.443  13.534  13.602  30  34  9  38  Table 3.2:  42  15  46  24 12.850  d. k  • Table  3.1 shows the exact d i s t o r t i o n of such p e r m u t a t i o n s for s m a l l values  of k. F i n d i n g dk for s m a l l k's (by c o m p u t i n g the eigenvalue corresponding to a l l permutations i n H.^ and t a k i n g the m i n i m u m ) suggests that df. converges to 7 + 4\/3. T a b l e 3.2 shows the value of d for different k's. k  Consequently we improve the result of K e n y o n et a l . [36] f r o m 3 + 2\/2 ~ 5.828 t o 13.602. Theorem 7. There exists a polynomial algorithm for computing the optimal distortion embedding between two line metrics, provided the optimal distortion does not exceed 13.602.  3.5  Computing Separability  G i v e n a p e r m u t a t i o n TT of size n one can compute its separability b y the following greedy a l g o r i t h m . I n i t i a l l y set x = 1. F i n d the largest nice interval [x,y] (in case x = 1 d o n ' t choose y = n ) , set x — y + 1, and repeat. Recursively find the o p t i m a l separation for each nice interval..  49  C  Theorem 8. The above greedy algorithm, is correct. Proof. It suffices to show that the first step is correct. A s s u m e / is the largest nice interval that contains x. Suppose a n o p t i m a l a l g o r i t h m OPT behaves differently; let I\, I2, • • • ,Ik be all intervals returned by OPT that have non-empty intersection w i t h I.  Since k > 2, because of the m a x i m a l i t y of I, we could take / and I  k  — I  instead of those k intervals i n O P T and get a better or equal separability consistent w i t h our greedy a l g o r i t h m . It is very easy to see that I  k  3.6  — I is a nice interval.  •  Pattern matching for permutations  T h e question of finding whether a p e r m u t a t i o n contains another p e r m u t a t i o n is of interest for many people because of its applications. It is sometimes called pattern matching i n t h e literature and comes as either a decision or a counting p r o b l e m : G i v e n two permutations a and TT decide if a contains TT or count the number of occurances of TT i n a. T h e greedy a l g o r i t h m for recognizing /c-separable permutations i n subsection 3.5 is a similar p r o b l e m : G i v e n a p e r m u t a t i o n TT, does it avoid a l l permutations i n Ilfe+i U  7r£  + 2  ?  Bose et al. [12] considered recognition of 2-separable permutations a n d proposed a n efficient a l g o r i t h m for b o t h the decision and counting p r o b l e m . T h e y also show that the general decision p r o b l e m is N P - C o m p l e t e and the counting p r o b l e m is # P - C o m p l e t e . A n alternative way to recognize non-2-separable graphs, as pointed out i n [12], is t o consider the corresponding p e r m u t a t i o n g r a p h . It' is not h a r d t o see that a p e r m u t a t i o n is non-2-separable iff its corresponding p e r m u t a t i o n graph is Pi-free, meaning that i t does not have any induced p a t h of length four. One can use the linear time a l g o r i t h m i n [21] to recognize Pi-free graphs. It doesn't seem  50  F i g u r e 3.4: A separation tree. to us that p e r m u t a t i o n graphs corresponding t o /c-separable graphs, for k > 2, have any particular structure. In proposing the linear time a l g o r i t h m , Bose et a l . [12] introduce a special ordered b i n a r y tree called a separation tree corresponding t o a p e r m u t a t i o n 7r of 1 to n w i t h the following properties: 1. Leaves are 7r(l),7r(2), • • • ,7r(/c) i n order. 2. F o r any node v, if the set of leaves of the subtree rooted at v is {7r(i), ix{i + 1), • • •, 7r(z + j)} then [i, i + j] must be a nice interval. A separation tree corresponding to the p e r m u t a t i o n ( 3 , 4 , 1 , 2 , 8 , 5 , 6 , 7 ) is depicted i n F i g . 3.4. S i m i l a r l y we c a n extend the definition of separation tree a n d allow i t t o be /c-ary instead of binary. T h e resulting tree is equivalent to /c-separable permutations.  Theorem 9. A permutation TT is k-separable iff it has a k-separation tree. Proof. G i v e n a /c-separable p e r m u t a t i o n ir, one can easily b u i l d a /c-separation tree. A s s u m e Ii, I2, • • • , I  k  are the k /c-separable nice intervals.  Recursively b u i l d a k-  separation tree for each Ij and then connect the roots of all these k trees t o a new root.  51  For the reverse direction, assume a /c-separation tree corresponding t o TT is given. It is obvious that the set of numbers i n the subtree rooted at the j actually the j  t h  t h  child is  /c-separable nice interval.  •  Bose et al. [12] use the separation tree and o b t a i n a d y n a m i c p r o g r a m m i n g a l g o r i t h m t o decide i f a n y 2-separable p e r m u t a t i o n TT is contained i n a (larger) p e r m u t a t i o n a. A recursive p r o b l e m instance i n their approach is given a sub-permutation a' = <T of a a n d any node u, that defines a subtree T , 1j  u  of the separation tree  associated w i t h TT, decide i f TT is contained i n a', where TT is the p e r m u t a t i o n U  U  corresponding t o T . u  N o t surprisingly, we can use a similar d y n a m i c p r o g r a m m i n g approach a n d c o m p u t e matchings for /c-separable permutations. Theorem 10.  Given a k-separable permutation TT and a permutation a of size n  and m, respectively, one can compute the number of matchings of TT in a in time 0(mn ' ). k+ 2  Proof. L e t M(u,i,j)  be the number of matchings of TT i n a' — a ^. 1  U  T o avoid  double c o u n t i n g , let's assume that i is used i n every m a t c h i n g , i.e for every m a t c h i n g (*i)*2)  •••  ,ik), n (i ) u  x  = i, for some x.  • A s s u m e that u has k children u\,u-2, • • • ,u  i n order of their appearance i n  k  TT , i.e. every element i n TT U  UX  is less t h a n every element i n TT , UX+1  i n fact, p a r t i t i o n e d into TTU^S. It can be easily proven that  M(u,i,j)=  II  M(u ,i ,i i  (ii,*2,—ifc) x=l,— ,k  52  x  x  x+  - 1)  for a l l re's. TT is, U  ( A s s u m i n g that  i\ = i and ik+i = j + 1-) W e basically p a r t i t i o n a — a '- into 1  1  7  k ranges [i ,ix+i — 1] (for x = 1, 2, • • • , /c — 1) and compute the number of matchings x  of each Ui into corresponding sub-permutation of T'. 0(n  f c _ 1  C o m p u t i n g M(u,i,j)  ) t i m e a n d there are 0 ( m n ) possibilities for it, i , j . 2  p r o g r a m m i n g approach takes time 0(mn ) k+l  to compute M(u,i,j)  u, i , a n d j. F i n a l l y , the value J2i=i • •• ^( o>h ) u  n  n  takes  Thus, a dynamic for all values of  equals the number of matchings  of 7T into T , where ito is the root of the corresponding separation tree.  One c a n  easily augment the a l g o r i t h m t o o u t p u t the actual m a t c h i n g or list all the possible matchings as well.  3.7  •  Sortable Permutations  A n o t h e r interesting topic related t o permutations is characterizing classes of permutations i n terms of whether they' are sortable using tools like stacks and queues. T h e simplest versions of this p r o b l e m were studied by Knuth[38] who i m a g ined the elements of a p e r m u t a t i o n being an i n p u t sequence t o a stack. A sequence of p u s h and pop operations results i n an o u t p u t sequence (the p o p p e d elements) a n d the question is w h a t i n p u t p e r m u t a t i o n can be sorted (yield an ordered o u t p u t sequence).  Tarjan[52], E v e n and Itai[23], and Pratt[42] generalized the model t o  allow m u l t i p l e stacks and queues. T h e answer to the simplest case is k n o w n : Single stack sortable permutations can be recognized i n linear time, are characterized b y the forbidden p e r m u t a t i o n . [2,3,1], a n d there are ( ")/(^ + 1) (the n 2  th  C a t a l a n number) of t h e m of length n .  O t h e r researchers have studied variations of stacks: A v i s and Newborn[7] considered a less powerful stack called POP  pop-stack i n w h i c h P U S H operations are as usual, b u t  operations, called MPOP, pop the entire stack. 53  T h e y provide enumeration  2  6  7 3  1  5  4  /, = <5} I, = {4} 2  6  7' 3  /, =12},;., = {U,7}  1  4— 5  /:, = (3},;„ = {l} y , = (4 5} !  1—2—3—4—5—6  f  ;  7  F i g u r e 3.5: 5-sortable p e r m u t a t i o n ('-' indicates coupling) answers w h e n we use u n l i m i t e d pop-stacks or we use a fixed number of pop-stacks i n series. Bose et al.[12] also interpreted 2-separable permutations as sortable p e r m u tations b y the following device. T h e p e r m u t a t i o n is originally o n a queue; each time we can pick a range of elements and reverse their order. Once we do so, all elements of that range are coupled and remain coupled forever. F o r other related results like parallel-stack sortable permutations the reader is referred to [5] or [11]. Here we give a n interpretation of /c-separable permutations i n terms of sorting. G i v e n a p e r m u t a t i o n 7r o n a queue, we are allowed to do the following operations: • E a c h t i m e we can pick u p to k consecutive ranges I\, I2, • • • , Ik of elements of 7T/. and sort t h e m . Once we do so, T h e entire sub-range I\ U I2 U • • • U h gets coupled and remains coupled forever. • W e are not allowed t o pick a p o r t i o n of a coupled range, however, we c a n reverse the order of elements i n a coupled range. L e t ' s call- the above sorting mechanism k-sorting. A 5-sortable p e r m u t a t i o n is shown i n F i g . 3.5.  •  Theorem 11.  54  k-separable permutations are exactly the class of permutations that are k-sortable. Proof. It is obvious that any coupled range should be a set of consecutive numbers i n 1 t o n, for i f not we won't be able to insert any element i n a coupled range any more. T h a t means there is a correspondence between fc-sorting steps and nodes of a separation tree.  Since we always pick at most k sub-ranges, the corresponding  separation tree is a fc-ary w h i c h is equivalent,to fc-separable permutations according to T h e o r e m 9. T h e other direction of the proof is simple. G i v e n any /c-separable p e r m u t a t i o n 7r, one c a n consider its separation tree a n d sort the p e r m u t a t i o n i n a bottom-up fashion. W h e n we. are at a node u, a l l its children are already sorted; since it has at most k children, we can swap the orderings of children to get a sorted p e r m u t a t i o n corresponding t o the sub-tree rooted at u.  3.8  •  Conclusions and Future Work  We considered the p r o b l e m of finding a m i n i m u m distortion embedding of one fixed line metric into another fixed line metric. A s a consequence, we studied properties of permutations under 'certain separability constraints, a n d discovered features of these permutations i n various contexts: forbidden permutations, metric embedding, p a t t e r n m a t c h i n g , and stack sorting. T h e m a i n open question that we w o u l d like to address is whether or not we can still find a parameterized solution for embedding two fixed line metrics. Notice that the p r o b l e m is N P - h a r d [29] w h e n the distortion is at least n , for some constant e, but is unresolved for smaller values of distortion. e  A l t h o u g h we proved that the idea of considering /c-separable permutations does  55  not a p p l y w h e n the o p t i m a l d i s t o r t i o n is greater t h a n 13.602, there is still some hope. One may consider a different class of permutations that are algorithmically useful. A n o t h e r i m p o r t a n t fact is that we are considering all permutations whereas only a few of t h e m are a candidate to be an o p t i m a l embedding. It seems to us that e x c l u d i n g permutations that cannot be an o p t i m a l e m b e d d i n g from the set of ^-separable permutations would be a major improvement to our work. A n o t h e r interesting problem is to look for parameterized approximate solutions. It appears that if we allow the o p t i m a l d i s t o r t i o n to be a p p r o x i m a t e d , we can easily avoid m a n y permutations and only look for simple (possibly A:-separable for s m a l l k) permutations.  56  Chapter 4  D-Width  4.1  Introduction  One of the most significant recent advances i n the field of algorithmics comes f r o m the G r a p h M i n o r s project of R o b e r t s o n and Seymour. I n a d d i t i o n t o being a major a d d i t i o n t o the structure theory of graphs, the tools developed d u r i n g their work i m p l y algorithmic results such as every minor-closed g r a p h property can be decided i n . p o l y n o m i a l time.  T h e most far-reaching algorithmic c o n t r i b u t i o n is the i n t r o -  d u c t i o n of g r a p h decompositions such as tree decompositions and measures such as tree-width, w h i c h have helped identify large classes of tractable instances of h a r d (e.g. NP-complete) graph problems. T h e key t o the algorithmic success of tree decompositions is that they are readily extendable t o a r b i t r a r y relational structures. B y considering tree decompositions of the background (or primal) graph, large classes of tractable instances of h a r d problems c a n be found for various structures i n c l u d i n g hypergraphs and d i rected graphs. T h e m a i n drawback of this approach is that often i n f o r m a t i o n is lost when considering the background graph, and this may be crucial. For instance, the  57  background graph of a directed graph is the undirected graph obtained by forgetting edge orientations. T h u s efficient solutions to problems like H a m i l t o n i c i t y cannot be found by this technique. In [34], J o h n s o n et al. attempted to rectify this (and address problems i n directed graph structure theory) b y i n t r o d u c i n g directed tree-width, a generalizat i o n of tree-width to directed graphs. A l t h o u g h they managed to demonstrate the algorithmic benefits of arboreal decompositions by p r o v i d i n g efficient algorithms for problems such as H a m i l t o n i c i t y and disjoint paths, their measure was a w k w a r d l y defined and not as well behaved as tree-width, m a k i n g i t difficult to extend to further results. Consequently, other measures such as D-width [48], D A G - w i d t h [10, 40], a n d K e l l y - w i d t h [31] have been introduced i n a n effort t o find a more practical generalization of tree-width to directed graphs. A l s o i n [34], Johnson et. al.  introduced a graph searching game t o p a r -  t i a l l y characterize directed tree-width. T h e game, similar to one that Seymour a n d T h o m a s used t o characterize tree-width [50], involves a robber who can r u n a r b i t r a r i l y fast in strongly connected components, and a set of cops who attempt t o capture the robber b y b l o c k i n g his escape routes and l a n d i n g on. h i m . J o h n s o n et al. show that i f G has directed tree-width k — 1 then k cops can capture the robber i n this game, and towards a converse, i f k cops can capture the robber o n G, then G has directed tree-width at most 3k — 2. I n a d d i t i o n , they show that the n u m ber of cops required to capture a robber cop-monotonely (i.e. vacated vertices are. never revisited by cops) is different f r o m the number of cops required to capture a robber w i t h o u t this restriction, and i f k cops have a w i n n i n g strategy, then 3k — 1 cops have a robber-monotone (i.e. the set of vertices the robber can reach is nonincreasing) w i n n i n g strategy.  A d l e r [1] further extended these results b y showing  58  that robber-monotone and robber-non-monotone cop numbers do not coincide, a n d that the robber-monotone cop number and the directed tree-width also differ. O n undirected graphs, the equivalence of the cops and robber game and treew i d t h is c r i t i c a l to the i m p o r t a n c e of tree-width as a measure of graph complexity. O n one h a n d , the game is a good indicator of s t r u c t u r a l properties of graphs. For example, acyclic graphs only require 2 cops to capture the robber, a n d the n u m b e r of cops required does not increase under t a k i n g of minors. O n the other h a n d , the equivalence of monotone and non-monotone strategies implies that the number of cops required can be efficiently c o m p u t e d . W i t h o u t a clean correspondence w i t h such games, it is difficult to establish similar results for directed tree-width, p a r t i c u l a r l y results that can be used to efficiently compute the exact directed tree-width of a graph. In this chapter, we further study D-width [48] and identify the class of d i graphs w i t h D-width one. We then study the game characterization of D-width and show that D-width is b o u n d e d above and below by the number of cops required i n certain versions of the cop-monotone game. In p a r t i c u l a r , we o b t a i n a non-trivial upper b o u n d for D-width w h i c h is computable i n p o l y n o m i a l time w h e n that b o u n d is constant. We also compare various parameters and show that there exist a r b i t r a r i l y b i g gaps between haven order, directed tree-width, and D-width. T h e chapter is organized as follows. In Section 4.2 we f o r m a l l y define the cops and robber game and the concepts we use throughout the chapter. In Section 4.3 we prove the equivalence of D-width and directed tree-width when D-width is one and provide several algorithmic applications of directed one trees. T h e n , i n Section 4.5 we compare D-width w i t h other parameters such as haven order a n d directed tree-  59  w i d t h . In the final section, we o b t a i n a non-trivial upper b o u n d for D-width a n d propose an a l g o r i t h m for c o m p u t i n g that b o u n d provided the b o u n d is constant.  4.2  Definitions  In this chapter we assume a l l graphs are finite a n d directed unless otherwise stated. W e use s t a n d a r d g r a p h theory terminology, see for example [22].  4.2.1  D-width  W e recall the definition o f D-width as defined i n [48].  Definition 3 (Strongly connected set). A subset S of vertices of a digraph G is called a strongly connected set if G[S], the subgraph induced by S on G, is strongly connected. Definition 4 (D-decompositions and D-width). A D-decomposition of a directed graph G is a pair (T,W)  where T is a tree and W — {Wt\t 6 V(T)}  is a  family of subsets ofV(G) such that for every strongly connected set S C V(G): (Dl)T\ :={teT\W r\S^$}^%,and s  t  (D2) The subgraph ofT with vertex setT\ and edges {e = (s,t) G T\W nW r\S s  0} forms a connected subtree of T.  s  t  /  On the other hand, an edge is included  only if both its end points contain same vertex u of S. The w i d t h of a D-decomposition (T,W) is the minimum k such that \Wi\ < k + 1 for all Wi  6  W. The D-width of a directed graph G is the minimum width over all  D-decompositions ofG.  60  F i g u r e 4.1 shows a d i g r a p h w i t h D-width one, together w i t h a n o p t i m a l Ddecomposition. One can verify the above c o n d i t i o n for a l l strongly connected sets:  {a}, {&}, {c}, {d}, {e}, {a,b,c}\ {a,c,d,e}, {a,b,c,d}, a n d {a,b,c,d,e}. a  b  c  d •<  e  F i g u r e 4.1: A d i g r a p h (left) w i t h its D-decomposition of w i d t h one (right).  A s D-decomposition is quite similar to tree-decomposition, it inherits a l l its s t r u c t u r a l properties that can be used for algorithmic purposes. For example, similar to the undirected variant [37], if a d i g r a p h has a D-decomposition of w i d t h w, then it has a  nice D-decomposition of w i d t h w. A D-decomposition (T, W) is nice if every  node i G V(T)  has either one child or two. If it has one child j then |Wj — Wj \ = 1.  Otherwise, i f it has two children j and k then W i = Wj =  W. k  In a d d i t i o n a d i g r a p h G w i t h D-width w has a related undirected chordal g r a p h G' w i t h tree-width w that captures the connectivity of G.  Lemma 9. For every digraph G of D-width w, there exists an undirected chordal graph.G' with treewidth w such that every strongly connected set in G is a connected set in G'. Proof. L e t (T, W) be a D-decomposition of G = (V, E) of w i d t h w. L e t G' = (V, E') where  E' = {(u,v)\3t s.t. u  G  Wt and v  G  W }. In other words, every set of vertices t  Wt is a clique i n G'. (T, W) is a tree-decomposition of G'. Moreover, every strongly connected set i n G is a connected set i n G'.  61  •  D-width has also the balanced-separator property similar to tree-width. Lemma 10. For every digraph G of D-width w and any subset W, there exists a subset X of at most w + 1 vertices such that every strongly connected component of G\X  contains at most ^p- vertices from W.  Proof. T h e proof is essentially similar to the undirected version. G i v e n a D- decomposition T o f G w i t h w i d t h w, let i be the deepest node (pick a n a r b i t r a r y node as the root) such that the sub-tree rooted at i has at least  vertices f r o m W.  It's clear that every strongly connected component of D\Wi has then at most vertices f r o m W.  4.2.2  ^ •  D i r e c t e d tree-width and haven order  Here we introduce some relevant notation f r o m [34].  G i v e n two disjoint subsets  Z and S of vertices of a d i g r a p h G, we say S is Z - n o r m a l i f every directed p a t h w h i c h starts a n d finishes i n S is either wholly contained i n S or contains a vertex i n Z. A l s o , given a directed tree T w i t h edges oriented away f r o m a unique vertex r G V(T) (called the root), we write t > e for t € V(T) and e G E{T) if e occurs on the unique directed p a t h f r o m r to t, and e ~ t if e is incident w i t h t. T h e following concepts were introduced i n [34] and [35]. Definition 5 (Arboreal (pre-)decompositions and directed tree-width). An arboreal pre-decomposition of a digraph G is a tuple (T, B, W) where T is a directed tree with a unique root, and B = {Bt\t G V ( T ) }  and W = {fVe|e G E(T)}  are sets  of subsets of V(G) that satisfy: (Rl)  B is a partition of V(G) into (possibly empty) sets such that B  r  root r of T, and 62  ^ 0 for the  (R2) Ife The for  G  width  E(T),  then Be  is W -normal or empty.  := |J{73 |r > e} t  e  of an arboreal pre-decomposition (T,B,W) is'the minimum k-such that  all t G V(T),  \B  t  U U ~ t ^ e l < k + 1. e  An  arboreal d e c o m p o s i t i o n is a  decomposition in which all B are non-empty, and the t  directed tree-width  pre-  of a di-  graph G, dtw(G), is the minimal width of all its arboreal decompositions. If, i n a d d i t i o n , an arboreal pre-decomposition satisfies: (R3)  For each t G V{T)  we can order the outgoing edges e i , e 2 , . . . such that for  i < j there is no edge i n G f r o m B^-  to  B^  we c a l l the decomposition good. In [35], J o h n s o n et al. c l a i m that an arboreal predecomposition can be transformed into a good one w i t h the same w i d t h , but this does not follow f r o m their results and remains an open p r o b l e m . T h e i m p o r t a n c e of this p r o b l e m , and indeed the m o t i v a t i o n for [35], arises f r o m the fact that the a l g o r i t h m i c results of [34] require a good arboreal d e c o m p o s i t i o n .  However,  the  d e c o m p o s i t i o n constructed i n the proof of T h e o r e m 3.3 of [34] is good, i m p l y i n g ' that their a l g o r i t h m i c results do hold. O u r second definition is m o t i v a t e d by a similar definition i n [50]. Definition  haven  6  ((Pre-)haven and  of order k is a function  3  haven-width).  Let G be a digraph. A  assigning to every set Z  union of strongly connected components of G\Z  C  V(G) with \Z\ < k, a  such that if X C Y C V(G) and  \Y\ < k then 3{X) is the union of all strongly connected components of G\X intersect 3{Y).  A  component of G\Z  haven  pre-  which  is a pre-haven such that B(Z) is a single strongly connected  for all Z  C  V(G) with \Z\ < k. The  is the largest k such that G has a haven of order k  63  haven-width  of G, hw(G),  In [50] it was shown that if an undirected g r a p h G has a pre-haven of order k t h e n i t has a haven of order k. T h e analogous question for directed graphs remains a n open p r o b l e m .  4.2.3  C o p s a n d robber game  We recall the definition of the cops a n d robber game defined i n [34]. T h e game is played o n a directed g r a p h G, by two players: one controlling a set of k cops [k is a parameter of the game), the other controlling a visible robber. T h e cops and t h e robber occupy vertices i n the g r a p h .  A move consists of the cop player  a n n o u n c i n g the next l o c a t i o n of the cops a n d then proceeding t o move the cops t o this l o c a t i o n . D u r i n g this, the robber c a n r u n at great speed along directed paths w h i c h do n o t contain any cops not being moved provided there is also a cop-free directed p a t h back t o his original s t a r t i n g position. I n other words, the robber may move t o ' a n y vertex i n the same strongly connected component of G \ X where X is the set of locations occupied by stationary cops. If a cop lands o n the p o s i t i o n of the robber t h e n the cop player wins, otherwise, i f the robber is able t o evade capture indefinitely, the robber player wins. M o r e formally, the game consists of positions (X,R)  where X C V(G), \X\ < k a n d R is either empty, or a strongly connected  component of G \ X. I n i t i a l l y the cop player chooses X$ C V(G). w i t h |Arj| < k and the robber player chooses a strongly connected component RQ of G \ X to give the i n i t i a l position,-(XQ,RQ).  If R ^ 0, a move, from p o s i t i o n (X,R),  consists of  the cop player choosing X' C V(G) w i t h \X'\ < k a n d the robber player choosing R', a strongly connected component of G \ X' such that R a n d R' are contained in' t h e same strongly connected component of G \ (X D X'). If at any point t h e robber is unable to choose such a strongly connected component, then R' — 0. T h i s  64  gives the next p o s i t i o n (X',R').  A play is a (possibly infinite) sequence of moves,  and i t is winning for the cop player if it is finite and has a final p o s i t i o n (X, 0) for some X, .otherwise it is winning for the robber. A play (XQ, RQ), (X\, R\),... cop-monotone i f the cops never revisit a vertex, that is for all h,i,j  is  w i t h h <i < j,  Xh f l Xj C Xi. T h e play is robber-monotone if Ri D Ri+i for all i. For any d i g r a p h G, we denote the m i n i m u m number of cops that are required to capture the robber w i t h a cop-monotone (resp. robber-monotone) strategy by cop-monotone(G)  (resp.  robber-monotone{G)). A s is usual for these types of games, we are p r i m a r i l y concerned w i t h w i n n i n g strategies. A (k-cop) strategy for the cop player is a tuple (Yo, TT) consisting of set Yo C V(G) w i t h |Y | < k together w i t h a function vr : T(V{G)) 0  V(V(G)),  x V(V(G))  -+  such that for X C V ( G ) w i t h \X\ < k if i ? is. a strongly connected com-  . ponent of G\X  then |TT(X,.R)| < fc, and 7r(X,0) = 0. A play  (X ,Ro),(X ,R ),... 0  is consistent w i t h a strategy (Yb,7r) if Xo = Yo and X j + i = it(Xi,Ri) a strategy is winning (cop-monotone,  1  1  for all i , and  robber-monotone) if all consistent plays are  w i n n i n g for the cop player (cop-monotone, robber-monotone respectively). Variants of the game where the robber moves first or only one cop can be moved at a time or the cops are lifted and placed i n separate moves are all equivalent i n that the existence of a w i n n i n g strategy for a given number of cops does not depend on the variant. For the results we present i n the following sections, we introduce the idea of a strategy forest. F i x G and k, and consider the directed g r a p h w i t h nodes labeled by positions i n the cops and robber game, and a n edge from (X,R) such a t r a n s i t i o n is possible under the rules specified above.  t o (X',R')  if  T h a t is, if R /  0,  a n d either R' = 0 or R and i ? ' a r e i n the same strongly connected component of  65  G \ (X n X'). W e call this the positional graph defined by G and k.  A strategy  a = (YQ,TT) w i l l define a s u b g r a p h IT^ of this g r a p h , consisting of a l l roots of the f o r m (Y , R), and edges ((X, R), (X',R')) if X' = n(X, R). W e also remove all edges 0  of the f o r m (X, 0).  If a is a w i n n i n g robber-monotone strategy, 11^ takes a very  simple f o r m .  Lemma 11. If a  —  (YO,TT) is a winning robber-monotone strategy, then U  a  is a  forest of rooted trees, with each root having a label of the form (Yo, -)• Proof. Since a is a w i n n i n g strategy, H  a  is acyclic and a l l its roots are of the f o r m  (Yo, _). T o show that it is a forest, we need only show that no node has more t h a n one predecessor.  Suppose (X',R') has two predecessors. These two predecessors  either have a c o m m o n ancestor (X, R) w i t h two distinct children (TT(X, R),RI) a n d (n(X, R), R2) or are descended f r o m two distinct roots (Yo,R\) a n d ( Y o , ^ ) such that i ? i n i ? 2 7^ 0- ( B y robber-monotonicity, the non-empty i ? ' i s a subset of i ? i D i ? 2 - ) B u t R\ a n d R2 are strongly connected components of G \ rr(X, R) (or G \ Yo), so R\ = R2, c o n t r a d i c t i n g the distinctness of the nodes.  •  W e call Ilfj the strategy forest associated.with a.  4.3  Directed One Trees  C u r r e n t l y there is no k n o w n p o l y t i m e recognition a l g o r i t h m for b o u n d e d D-width digraphs. F o r the special case that D-width is one, however, there is a fast recognit i o n a l g o r i t h m based o n a s t r u c t u r a l characterization of such digraphs. Moreover, we prove that directed tree-width and D-width coincide i n this case. T h i s result is achieved b y c o m p a r i n g b o t h measures t o the haven order.  "  .  66  F i r s t , we prove the following theorem relating haven order a n d D-width of directed one-trees.  Theorem 12. A digraph G has D-width one if and only if it has haven order two. Proof. If G has a haven B of order at least 3 then the robber can w i n against two cops b y staying at B(X) where X is the p o s i t i o n of cops. Hence, b y T h e o r e m 17, G must have D-width at least two. Since this is not the case, G has haven order at most two. B u t , the haven order of G cannot be one because G has a cycle (otherwise its D-width w o u l d be zero) a n d , thus, G has haven order at least two. (Simply set /3(0). = C a n d let B({x}) be a strongly connected component the contains a vertex of C — {x}, where C is a cycle i n G.) Consequently G has haven order exactly two. N e x t , we show i f G has haven order two then its D-width is one. It suffices to prove this for strongly connected G since i f G has haven order two a n d D-width d, it contains a strongly connected component w i t h haven order two a n d D-width  d. T h e proof is by i n d u c t i o n o n the number of vertices of G. B y L e m m a 12, G contains a vertex u w i t h out-degree (or in-degree) one. Suppose u has out-degree one (the in-degree one case is handled similarly) w i t h edge (u, v) being its only outgoing edge. C o n t r a c t the edge (u, v), by removing u and connecting all u's i n c o m i n g edges to v (and ignoring loops i f created), t o o b t a i n a new d i g r a p h G'. B y L e m m a 13, G' has haven order at most, two a n d , according t o the i n d u c t i o n hypothesis, has D-width at most o n e . L e t T' be a D-decomposition of G' w i t h w i d t h at most one. 1  A d d a new node r to T " w i t h W = {u, v} and attach it to a node of T " that contains r  v. It is easy to verify that the resulting D-decomposition is a proper one for G a n d has D-width one because if S is a strongly connected set i n G and u G S then S — {u} Hi G' has haven order one then it is acyclic and trivially has D-width zero.  is a strongly connected set i n G' and v G S.  •  Lemma 12. If G is strongly connected and has haven order two then G contains a vertex with in-degree or out-degree one. Proof. For any vertex u, a strongly connected component C of G \ {u} is called a  .u-root if there is no edge f r o m a vertex i n another component of G \ {u} to a vertex in  C. S i m i l a r l y we say a component C is a u-leaf if there is no edge f r o m C to any  other component. L e t rootleaf(u) be the m i n i m u m size over all iz-root and 'u-leaf components of G \ {u}. If rootleaf(u) = 1 for some vertex u, then there is a single vertex v w i t h either out-degree or in-degree one (to or from u). Otherwise, rootleaf(w) is at least two, for all  u.  In this case, we show that G has haven order at least three, a contradict i o n . L e t u be the vertex w i t h m i n i m u m rootleaf(u) and C be the component that u  minimizes rootleaf('u), i.e.  \C \ = rootleaf(u). U  Assume, w i t h o u t loss of generality,  that C is a u-root component. Notice that such components do exist as the graph u  whose vertices are strongly connected components of G\{u} and whose edges are G A,3v G B s.t. (u,v) G G} is acyclic.  {(A,B)\3u  It's roots are -u-roots and its  leaves are u-leaves. L e t /3(x) , for any single vertex x, be the strongly connected component of 2  G7\{x} that contains C , if x $ C , and the strongly connected component of G\{x} u  u  that contains u, otherwise. Let P{{x,y}) be the strongly connected component of G \ {x, y} that contains B(x) D B(y). We argue that B is a haven of order three. It is sufficient to show that B(x) n B(y) ^ 0 for all x and y. If x and y are b o t h i n C , then b o t h B(x) and B(y) have vertex u i n c o m m o n . Similarly, if b o t h u  2  I n w h a t follows we use  3{x) for 0({x}). 68  are i n G \ C ,  t h e n b o t h B(x)  u  For the  final  and B(y) G C  u  C. u  and y G G \ C ,  it suffices to show that  u  contains at least one vertex f r o m C .  that contain at least one vertex f r o m C , u  (At least one such component must exist because \C \ U  > 2.)  i n topological order. I f any Si contains u  then we're done. Otherwise, each Si contains only vertices f r o m C  u  path from v G G \ C  to a vertex i n C  u  u  u-root). T h u s , \Si\ < \C \. U  vertices i n C  \ {x}  u  contains u (a consequence of C  u  being a  is supposedly the smallest such component.  u  u  because every  We show that some 'Si is an x-root or x-leaf component.  T h i s is a c o n t r a d i c t i o n since C For all y G C \  B(x)  L e t S\, S2, • • • Sk be the. strongly connected  u  components of G\{x}  share  {x},  there exists a p a t h f r o m u to y that contains only  (in particular, that doesn't contain x).  If not, then the first  component Si (smallest i) that contains such a y is an x-root, a c o n t r a d i c t i o n . Since C  u  is a ix-root and x G C , u  z to u that doesn't contain x. vertex z G G\C , u  for all z G G \ C , u  there exists a p a t h f r o m  Hence Sk cannot have an outgoing edge (y,z)  to a  otherwise y, z, and u w o u l d be strongly connected v i a paths that  d o n ' t contain x. T h i s implies that Sk is an x-leaf, a contradiction.  •  Lemma 13. If G' is a digraph obtained by contracting an edge (u,v), with u having out-degree one orv having in-degree one, in a digraph G then H(G') < H(G), where H{G) is the haven order of G. N o t e : T h e same statement regarding directed tree-width of G and G'  was  noted by J o h n s o n et al. [34]. Proof. L e t B' be a haven of order w for G'. for G.  We construct a haven, 8, of order w  F i r s t , assume u has out-degree one. For any subset Z of vertices i n G, if  u E Z, let U(Z)  = (Z-  {u})  U {v},  otherwise let U(Z)  69  = Z.  For Z w i t h \Z\ <  w,  let 3(Z) be the strongly connected component of G that contains 3'(U(Z)). \U(Z)\ < \Z\ so 3'(U(Z))  is defined.)  (Note:  If C is a strongly connected component  of G' \ Z for some Z a n d u £ Z then either C or C U { i t } is a strongly connected component  of G\Z. T h u s , 3{Z) equals either 3'(U{Z)) or / 3 ' ( [ / ( Z ) ) U { i x } . Therefore,  for a n y two subsets  Z\ C Z of less t h a n 2  /3(Zx) D / 3 ( Z ) D /3'(C/(Zi)) n 3'(U(Z )) 2  2  i« vertices of G,  XJ(Z\) C XJ{Z \ so 2  = 3'{U{Z )) # 0. T h u s , 3{Z ) C /3(Zi). 2  2  N o t i c e that i f C i a n d C are two strongly connected componets of G\Z\ a n d G\Z , 2  respectively, t h e n either C  2  2  C C i or C i D C 2 = -0. T h e case w h e n v has in-degree  one is similar.  •  Corollary 3. The three statements "G has D-width one", G has directed tree-width a  one", and "G has haven order two" are equivalent. Proof. T h i s follows f r o m 12 a n d the following two theorems f r o m [34] a n d [47]. Theorem 13 (Johnson et al. [34]). H(G) - 1 < tree-width(G) < 3H(G) + 1 for digraphs G, where H(G) is the haven order of G. Theorem 14 (Safari [47]). For any digraph G, tree-width(G) < D-width(G).  • 4.3.1  Algorithmic results  T h e nice p r o p e r t y of directed one-trees is that they have a contractible edge as per L e m m a 12. W e c a n use this property t o design recursive algorithms for certain problems o n directed one-trees. In the following algorithms, we assume that the contractible edge is (it, v) ( w i t h u h a v i n g out-degree one). W e contract t h e edge b y r e m o v i n g u a n d con-  70  necting all it's i n c o m i n g edges t o v. T h e case when u has iri-degree one is handled analogously.  Recognition  T o find a D-decomposition w i t h w i d t h one, i f i t exists, i n a d i g r a p h  G: 0. If G is a single vertex r e t u r n a single node containing the vertex. 1. F i n d a contractible edge  (u,v), contract it, and o b t a i n a new d i g r a p h G'.  If no contractible edge exists then F A I L . 2. Recursively find a D-decomposition T' for G'. 3. L o o k for a node of T' that contains v, and add a new node r t o i t w i t h  W = {u, v} r  If we keep the list of vertices ordered by in-degree and also by out-degree, we can p e r f o r m steps 1, 2, and 3 i n 0(n) time. T h u s , the t o t a l r u n n i n g time is 0 ( n ) . 2  Hamiltonian cycle  T o find a H a m i l t o n i a n cycle, if it exists, i n a directed one-tree  G i n 0 ( n ) time: 2  0. If G is a single vertex r e t u r n the vertex. If G is acyclic then F A I L . 1. F i n d a contractible edge  (u,v), contract it, and o b t a i n a new d i g r a p h G'.  A l s o remove all edges (x, v) i n G' where (x, v) is a n edge i n G. If no contractible edge exists then F A I L . 2. Recursively find a H a m i l t o n i a n cycle C i n G'. 3. Replace the edge (x,v) i n C w i t h (x,u),(u,v) t o o b t a i n a H a m i l t o n i a n cycle for G'.  71  4.4  Comparing D-width and directed tree-width  It is conjectured i n [48] that D-width and directed tree-width are equal. We disprove this conjecture i n this section and prove that there is an a r b i t r a r i l y gap between Dw i d t h and directed tree-width, though it is s t i l l u n k n o w n whether the two are w i t h i n a constant factor of each other. W e w i l l also provide several inequivalence results for other relevant parameters such as haven order. T o this a i m , we consider game characterizations of D-width and directed tree-width. Theorem 15. For every digraph G,  tree-width(G) < robber-monotone(G) < cop-rnonotone(G) < D-width(G)  Proof. tree-width(G)  <  robber-monotone(G)  It is proven in. [34]. robber-monotone(G)  <  cop-monotone(G)  L e t a = (YQ,TT) be a cop-monotone w i n n i n g strategy, then we c l a i m a is a robbermonotone w i n n i n g strategy.  A s s u m e not; we show t h e robber can defeat a b y  m o v i n g t o a vacated vertex, c o n t r a d i c t i n g the assumption t h a t a is w i n n i n g . L e t p = (XQ, RQ), (X\, Ri),... some i. r E Xi\  be a play consistent w i t h a such that Ri J72 Ri+l for  F r o m the definition of a play, it follows there exists r 6 R4+1 such that Xi i. +  L e t p' = (X , R' ), (X[, R' ),... 0  Q  x  be a play consistent w i t h a that  agrees w i t h p u p t o ( X j + i , Ri+i), such that r G R'j for all j > i. N o t e that since r G Ri+i and a is cop-monotone, such a play exists as there w i l l always be a strongly connected component containing r. B u t then this play is not w i n n i n g for the cop player.  72  cop-monotone(G) < D-width(G) A s s u m e a D-decomposition (T, W) of G of w i d t h k. is given. L e t T be rooted at a node r.  T h e cops c a n start at XQ = W . R  w i t h roots r\,r2, • • • ,r , m  L e t T\,T2, • • • ,T  m  be subtrees of T  children of r. L e t Ui be the u n i o n of the sets Wj over a l l  nodes j i n T ; . A c c o r d i n g to conditions of D-decompositions, the robber c a n o n l y be at vertices i n one of the sets U.  T h e cops c a n move t o W  Ti  a n d continue t h e  strategy u n t i l they t r a p the robber i n one of the leaves. T h e connectivity c o n d i t i o n of D-decompositions ensures that this strategy w i l l be strongly cop-monotone.  4.4.1  •  A r b i t r a r y gap between different games  W e first observe t h a t there c a n be a n a r b i t r a r i l y b i g gap between t h e n u m b e r of cops required t o w i n b y using different strategies i n the cop/robber game.  Theorem 16. For any m G N there exists: 1. A digraph on which 4 m cops can capture a robber, but 5 m cops are required to capture it with a robber-monotone strategy. 2. A digraph on which 4 m cops can. capture a robber with a robber-monotone strategy, but 5 m cops are required to capture it with a cop-monotone strategy. Before we prove T h e o r e m 16, we need to introduce the n o t i o n of lexicographic product. Definition 7. Let G and H be digraphs. The lexicographic p r o d u c t , G • H, is the  graph with V(G • H) = V(G) x V(H) and E(G •H) = { ((x,y), (x',y'))\(x, x') G E(G), or x = x' and (y, y') G E{H)}. T h e proof relies o n the following result, similar to one presented i n [32]. 73  Lemma 14. Let G be a digraph, K  m  the complete digraph on m vertices. At least  k cops have a (cop-monotone, robber-monotone) winning strategy on G, if and only if at least mk cops have a (cop-monotone, robber-monotone respectively) winning strategy on G • K . m  Proof. If k cops have a w i n n i n g strategy on G, then a w i n n i n g strategy for mk cops on G • K  m  is obtained by s i m u l a t i n g the game o n G. If the robber's p o s i t i o n is  (r, s) E V(G • K )  then we position a robber o n r E V(G).  m  cops' play o n  G and play o n G • K  m  by placing  whenever a cop w o u l d be placed o n x E V(G).  W e then consider the  n cops o n {{x,y)\y  E  V(K )} m  It's easy t o verify that the cop-  m o n o t o n i c i t y and robber-monotonicity of the strategies do not change. For the converse we show that if the robber can defeat k — 1 cops on G then he can defeat mk — 1 cops on G • K . m  A g a i n we simulate the game for G • K  m  G, b u t this t i m e f r o m the robber's perspective. W e place a cop o n x E V(G) if all vertices i n  V(G • K ) of the f o r m (x,y), y m  E  on only  V(K ) are occupied. B y the m  pigeon-hole principle, this requires at most k — 1 cops o n G. T h e robber's current p o s i t i o n is projected as before. T h e robber's response r' o n G is lifted t o G • by p l a y i n g t o a non-occupied vertex of the f o r m simulated game, at least one such vertex exists.  K  m  (r',y). A s r' is unoccupied i n the A s the robber can defeat k — 1  cops o n G, the strategy is w i n n i n g . T o complete the proof we need t o show that if a strategy is not (cop-monotone, robber-monotone) o n G then its corresponding strategy o n G • K  m  is not (cop-monotone, robber-monotone respectively) either.  T h e idea is that if the robbers play according to the above strategy then the cops either need t o occupy all vertices of type  (x,r), for any x, i n G • K  m  or none of  t h e m . P a r t i a l l y filling these vertices doesn't impose any constraint on the robber's movement a n d , hence, is not useful.  It's now very easy t o verify that if such a 74  F i g u r e 4.2: G r a p h on w h i c h 4 cops have a w i n n i n g strategy but 5 cops are required for robber-monotone strategy.  F i g u r e 4.3: G r a p h on w h i c h 4 cops have a robber-monotone w i n n i n g strategy but 5 cops are required for cop-monotone strategy. strategy is (cop-monotone, robber-monotone) on G • K  rn  then it's corresponding  strategy on G is (cop-monotone, robber-monotone respectively).  •  W e now t u r n to the proof of T h e o r e m 16. Proof. In [1] it was shown that 4 cops have a w i n n i n g strategy on the graph i n F i g u r e 4.2, b u t 5 cops are required to capture the robber w i t h a robber-monotone strategy.  In [34] it was observed that 4 cops have a robber-monotone w i n n i n g  strategy on the graph i n F i g u r e 4.3, but 5 cops are required to capture the robber w i t h a cop-monotone strategy. T h e results then follow by t a k i n g the lexicographic p r o d u c t of these graphs w i t h K , m  the complete graph on m vertices.  75  •  4.4.2  A r b i t r a r y gap between D - w i d t h , directed tree-width,  and  haven order Theorems 15 a n d 16 immediately yield a n a r b i t r a r y b i g gap between directed treew i d t h a n d D-width.  In this section we study the behavior of D-width, directed  tree-width a n d haven order under lexicographic p r o d u c t a n d independently prove the existence of a n a r b i t r a r y b i g gap for the above three parameters. We first prove that D-width behaves well under lexicographic p r o d u c t .  Lemma 15. If G is a digraph, and K  m  the complete graph on rn vertices, then  1 + D-width{G • K ) = m • (1 + D-width(G)). m  Proof. O n e can view G»K  m  as m a k i n g a clique  {u\, u , • • • , u } out of every vertex 2  u of G a n d connecting Ui t o VJ i f a n d only i f (u,v) decomposition of w i d t h as follows. W  m  G E(G).  L e t (T,W)  w of G. W e construct a D-decomposition (T, W') of G»K  m  is a family of subsets of vertices of G • K  m  such that for any j a n d  i, Uj G W[ if a n d only if u 6 W{. It c a n be easily proven that (T, W) D-decomposition of G • K  m  let  be a D-  is a proper  a n d has w i d t h m(w + 1) — 1. F o r the reverse direction,  (T',W') be a D-decomposition of G • K  m  of w i d t h  w' such that Y2ieT<  *  s  m i n i m i z e d . W e first make the following observation.  Claim 1. For every u G G and i G T, either U C W{ or U D W[ = 0, where U = {ui,u , • • • ,u }. 2  m  Proof. A s U is a clique i n G • K , there must be a node j w i t h U C W j . L e t % be rn  the furthest node f r o m j that violates the above condition, i.e. there are u , u p  w i t h Up G W[ a n d u  q  q  GU  G" W[. L e t k be the node before i i n the unique p a t h f r o m j t o  i i n T ' . W e c l a i m that d r o p p i n g u f r o m W[ still leaves a proper D-decomposition p  c o n t r a d i c t i n g the assumption that  YlieT' 1^71 ^ m i n i m u m . If not, there must be a s  76  strongly connected set S such that vertices of S do not make a connected subtree i n the new D-decomposition (obtained by d r o p p i n g u  from W(). T h i s is possible  p  only i f 5 Pi W[ D W' = {u } a n d there are some vertices of S other t h a n u i n W[. k  p  p  B u t , then, the strongly connected set  (S U {u })\{u } p  subtree i n t h e original D-decomposition.  does not make a connected  q  A s i is t h e furthest node f r o m j w i t h  0 < \U f l W(\ < m, i is a leaf of the subtree that contains u  (if a further node  1 contained u  is not connected)  p  p  then \W[ D U\ = m a n d thus u  q  and, hence, d r o p p i n g u  p  E W[ so T " |  U(J  f r o m W' does not violate conditions (D\) a n d (-D2) for L  T'\ .  •  Up  N o w , given a D-decomposition w i t h the above property we can replace every node that contains a l l vertices of U b y u a n d o b t a i n a D-decomposition of G w i t h width  - 1.  •  m ' A similar result holds for haven-width:  Lemma 16. If G is a digraph, and K  m  the complete graph on m vertices, then  hw(G • K ) = m • hw(G). m  Proof For this proof we define a function / : T(V(G»K ))  -* V{V{G)) b y f{X') =  m  {v\(v,k) E X' for a l l k E V(K )}. rn  F i r s t we show that if. G • K  m  8, of order mk then G has a haven, 8', of order k.  J{8{X x V{K ))).  N o w as 8(X x V(Km))f](X  m  8(X x V(K )) m  has  x  has a haven,  W e define 8' as 8'(X)  = 0, every vertex (x,y)  V(K )) m  x £ X. B u t then, since 8(X x V(K )) rn  component ( m a x i m a l strongly connected set), {x} x V(K ) m  = E  is a strongly connected C 8(X x V(K )) for m  each such x, so /3'(X) is non-empty a n d strongly connected. B y observing that i f XQY  then f(X)  C / ( Y ) , we see that B'(X) 5 ^ ' ( y ) whenever  77  XQY.  For the converse, we show that if G has a haven, 8, of order k then G • has a haven, /?', of order mk.  F o r this we define B'{X)  K  m  = (3(f(X)) x V ( i v ) ) \ X . m  B y the pigeon-hole principle, if | X | < mk then | / ( X ) | < k, so 8' is well-defined o n sets  X with  f(X).  Thus  < m/c. Since  8 is a haven, 8(f{X)) is non-empty and disjoint f r o m  B(f(X)) x V^i^m) has elements (x',y) such if (x,y) G X , there exists  .z G V ( i f ) such that (x,z) m  $ X. T h u s 8'(X)  A g a i n , the m o n o t o n i c i t y of / implies B'(X)  is non-empty and strongly connected. 2 8'{Y)  whenever X CY.  •  Unfortunately, directed tree-width is not obviously so well behaved. However, by replacing vertices i n an arboreal decomposition by cliques, we o b t a i n one direction of the analogous result.  Lemma 17. If G is a digraph, and K  m  1 + dtw(G»K ) m  tJie complete graph on m vertices, then  < m - ( l + dtw(G)).  We observe that the graph i n F i g u r e 4.3 has directed tree-width 3, D-width 4, and haven-width 4, g i v i n g us a n a r b i t r a r y gap between D-width, directed tree-width and haven-width.  Corollary 4. For any m G N there exists: 1. A graph with D-width 5 m — 1 and haven-width Am> and 2. A graph with D-width 5 m — 1 and directed tree-width < 4 m — 1  4.5  Upper Bounds for D-width  So far, we know some lower bounds for D-width, namely, directed tree-width, haven order, cop-monotonicity, a n d bramble n u m b e r . 3  3  T h e bramble number result appears in [48]. 78.  In this section we o b t a i n a non-  t r i v i a l upper b o u n d for D-width w h i c h is computable i n p o l y n o m i a l time when Dw i d t h is constant. U n f o r t u n a t e l y there doesn't exist any a l g o r i t h m for c o m p u t i n g o p t i m a l or nearly o p t i m a l D-decompositions.  However, using the results of this  section along w i t h those of the previous section, we can compute non-trivial upper a n d lower bounds for D-width. We prove that D-width is at most the number of cops required for a restricted cop-monotone w i n n i n g strategy that we call  strongly cop-monotone.  Definition 8. A strongly cop-monotone strategy ix is a cop-monotone strategy with the additional constraint that ir(X, R) C X U R. Theorem 17. Let G be a digraph. Then, if k + 1 cops have a strongly cop-monotone winning strategy on G then the D-width of G is at most k. Proof. L e t a  —  (YQ,TT) be a w i n n i n g strongly cop-monotone strategy for  F r o m T h e o r e m 15, a must also be robber-monotone. Let U  a  k + 1 cops.  be the strategy forest  associated w i t h a. W e define a D-decomposition (T, W) as follows:  1. V(T) = 2.  V(U )u{r}; a  E(T) = E{lA ) U {(r,t)\t is a root of n } ; a  4  a  3. W = Y ; a n d W = ir(X, R) for t = (X, R) 6 V(U ). r  0  t  a  It is clear that (T, W) has w i d t h at most (k + 1) — 1 = k. Because a is a w i n n i n g strategy, every vertex must be occupied by a cop at some point, so for every strongly connected set S, T\  s  connected set.  = {t\W n S ^ 0} ^ 0. For c o n d i t i o n (D2), let S be a strongly t  F r o m the construction of Ii  a  and the strong cop-monotonicity of  cr, for any situation {Y ,Rn) such that S n ixiY^^Rn) ^ 0, there is a unique p a t h n  4  F o r the decomposition to be undirected we ignore the directions on the edges in LTo79  (Yo,Ro),(Y ,R ),...,(Y ,R ) 1  1  n  n  such that S n ir(Yi,Ri)  ^  0, for 0 < i < n and  S C RQ. Moreover, (YO,RQ) is c o m m o n i n all such paths regardless of  (Y ,R ). n  n  Hence, i t suffices t o show that 5 remains connected along paths of n ^ . B u t this follows i m m e d i a t e l y f r o m the cop-monotonicity of a: i f the cops occupy some of S, leave all vertices i n S, and then occupy some of S, either they revisit a vertex (contradicting cop-monotonicity), or the robber can defeat a o n S (contradicting the fact that a is w i n n i n g ) .  • 4.5.1  C o m p u t i n g the strongly cop-monotonicity  Theorem 18. Given a digraph G and an integer k, determining if k cops have a strongly cop-monotone winning strategy on G can be decided in time 0(n ), k+3  where  n — | V ( G ) | . Furthermore, the algorithm will find such a strategy if one exists. Proof. T h e a l g o r i t h m we present i n F i g u r e 4.4 recursively computes a k-cop strongly cop-monotone strategy TT from position (X, R) by iterating t h r o u g h all possible v a l ues for X' w h i c h preserve monotonicity, and then checking that there is a w i n n i n g strategy from (X , R') for all R' w i t h a non-empty intersection w i t h R. T h e correct1  ness and r u n n i n g time of this a l g o r i t h m follow i n the next two lemmas.  •  Lemma 18 (Correctness). Given a digraph G and an integer k, TT = strategy (0, G, G, k) is a k-cop strongly cop-monotone winning strategy if, and only if, such a strategy exists. Proof. T o show that the a l g o r i t h m computes a strongly cop-monotone w i n n i n g strategy, we first show that the computed strategy is strongly cop-monotone and then prove that i t is a w i n n i n g strategy.  For every (X, R), ir(X,R) 80  C X U R, so TT is  Algorithm strategy(X, R, G, k) foreach X' C X U R with X' ± X, \X'\ = k do L e t R\, i ? 2 , • • •, Rrn be a l l strongly connected components of G\(X' n X) that have nonempty intersection w i t h R V i , let <7j = strategy(X , R4, G, k) f  if <7j ^ 0 , V i , then r e t u r n a = ( X , 7r) where IT(X,R) = X' a n d cr follows Ui i f the robber moves t o R4.  end return 0 F i g u r e 4.4: F i n d i n g a strongly cop-monotone w i n n i n g strategy  strongly cop-monotone. T o show that the strategy is w i n n i n g , we show that i t is  (X,R).  w i n n i n g f r o m each p o s i t i o n  T h i s is easily established by i n d u c t i o n o n the  size of R, as TT(X, R) is defined as a set X' such that the strategy is w i n n i n g f r o m (X',R') for a l l reachable positions X y£ X' C XuR,  (X',R').  A s we observed above,  R' C R, a n d as  X' w i l l include vertices from R, so R! w i l l be s t r i c t l y smaller t h a n  R. For the converse, we need to s h o w ' t h a t i f there is a &>cop strongly copmonotone strategy  a' =  {YQ,IT') then  ir'(X, R) is a possible r e t u r n value for ir(X, R).  W i t h o u t loss of generality, we can assume TT'(X, R) C X U R a n d \TT'(X, R)\ = k as we c a n always t r a n s f o r m a' into a strongly cop-monotone strategy w h i c h does satisfy these. F r o m T h e o r e m 15, a' is also a robber-monotone strategy, so R is a strongly connected component of G  \ (X n rc'(X, R)). F i n a l l y , it is clear that i f R' is a n o n -  e m p t y strongly connected component of G \ 7 r ' ( X , R), then TT'(TT'(X, R), R') ^ 0.  •  Lemma 19 (Running time). Given a digraph G and an integer k, strategy(0, G, G, k) runs in time 0(n ), k+2  where n = \V(G)\ .  Proof. W e implement the a l g o r i t h m using d y n a m i c p r o g r a m m i n g . T h e r e is a n entry (X, R) i n the d y n a m i c p r o g r a m m i n g table n for each subset of k vertices X a n d each  81  strongly connected component R of G\X.  T h e table is filled i n increasing order of  the size of R. A s there are at most n strongly connected components i n G\X, at most  0(n ) k+1  possible 0(n ) k  possibility for any  there exist  (X, R) pair. I n c o m p u t i n g rt(X, R) we t r y a l l  subsets X' of X U R and, for each one, i t takes 0 ( n ) t i m e to check 2  if C is a strongly connected component of G\(X  n X')  (using depth-first search).  Since each R4 is smaller t h a n R, we can use d y n a m i c p r o g r a m m i n g (or memoization) so that the check of 7r(X',Ri)  takes constant time' (after its i n i t i a l calculation). I n  t o t a l , the r u n n i n g time of the a l g o r i t h m is  0(n ). k+2  • 4.6  Conclusion and Future Work  In this chapter we further study D-width a n d identify the class of digraphs w i t h D-width one. W e also o b t a i n non-trivial upper bounds for D-width i n terms of the number of cops that are required t o capture the robber i n (strongly) cop-monotone cops/robber games. A s D-width is a n upper b o u n d for directed tree-width, not only does D-width inherit a l l the algorithmic advantages of directed tree-width, such as a n efficient a l g o r i t h m for H a m i l t o n i a n cycle o n bounded D-width graphs, b u t the s i m p l i c i t y of D-decompositions m a y also be used to establish other algorithmic results for digraphs w i t h b o u n d e d D-width.  F i n d i n g an a l g o r i t h m for c o m p u t i n g o p t i m a l or  nearly o p t i m a l D-decompositions would have a direct effect on the efficiency of these solutions. E x p l o r i n g the class of problems that are efficiently solvable o n bounded D-width graphs is also a very interesting direction of future research.  82  Chapter 5  Hyper-D-width 5.1  Introduction  I n this, chapter, we introduce  hyper-D-width and hyper-T-width as the first stable  (see definition 9) measures of connectivity for hypergraphs.  A f t e r s t u d y i n g some  of their properties a n d , i n particular, proposing a n a l g o r i t h m for computing-nearly o p t i m a l hyper-T-decomposition when hyper-T-width is constant, we introduce some applications of hyper-D-width a n d hyper-T-width i n solving h a r d problems such as the m i n i m u m vertex cover.  5.2  Background  In this section, we review the definitions that we use i n this chapter. A hypergraph H = (V, E) consists of a set of vertices V a n d a set of edges E where every edge e €  E is a subset of V. A path i n i f is a sequence of vertices u\, U2, • • • , u  m  such  that Ui a n d Ui+i are b o t h i n some edge i n H for i = 1, 2, • • • , m — 1. W e say u is  connected to v i f there is some p a t h from u to v. A set S of vertices is connected if  83  every two vertices i n it are connected. A connected component of H is any m a x i m a l connected set of H. F o r a subset X of V, the h y p e r g r a p h induced by X, by  H[X], is (X,E')  t  where  denoted  E' is the set of edges i n E all of whose vertices are i n  X. F i n a l l y , the h y p e r g r a p h H\X is H[V\X].  Notice our different interpretation of  connectivity i n this C h a p t e r . G i v e n an edge e =  {u\,v , • • • ,i>fc}, we consider i t as 2  a single connected unit meaning that e collapses by removing any of vis.  T h i s is i n  contrast w i t h those definitions that define connectivity based on the p r i m a l graph. T h r e e graphs are often associated w i t h any h y p e r g r a p h the  H: T h e primal graph,  dual graph, a n d the incidence graph. T h e p r i m a l graph is obtained by m a k i n g  a clique out of the vertices i n every edge i n H. T h e d u a l g r a p h is obtained by representing every edge by a vertex and connecting two vertices if their corresponding edges intersect.  T h e incidence graph is a bipartite graph whose first part corre-  sponds t o vertices i n H and whose second part corresponds t o edges i n i f . A vertex u i n the first part is connected t o a vertex e i n the second part iiu  € e i n H. T h e  tree-widths of the p r i m a l , d u a l , and incidence graphs are often referred to as primal,  dual, a n d the incidence tree-width, respectively. A famous example of using hypergraphs is using t h e m t o m o d e l inputs to the S A T p r o b l e m . A boolean f o r m u l a i n conjunctive n o r m a l f o r m w i t h clause sets  C\,C%, • • • ,C  rn  of variables  X = {xi,x , • • • ,x ] and their negations x~i,x~2, • • • ,x^ 2  n  is modeled by a h y p e r g r a p h H = (X, E) where E = {e\, e , • • • , e } 2  x\. 6 ej iff either x  k  m  and, for all k,  6 Cj or x^ 6 Cj.  For example, for ip = (a V b V c) A (a V c) A (6 V c) A 6, the corresponding h y p e r g r a p h is  H = ({a, b, c], {{a, b, c}, {a, c}, {b, c},{b}}).  For these formulas, the tree-width of the incidence graph seems to be the most general parameter for which the S A T p r o b l e m is fixed parameter tractable.  84  Theorem 19.  [51] Satisfiability of clause-sets with bounded incidence tree-width is  fixed-parameter tractable. . A p r o b l e m is fixed parameter tractable, if it a d m i t s an a l g o r i t h m w i t h r u n n i n g time 0(f(k)n ) a  where k is some parameter independent of n, f is any function of  k, and a is a constant independent of k and n. A s k doesn't appear i n the exponent of n, instances of large size n can be solved efficiently. Such a fact was already k n o w n for p r i m a l tree-width [27], b u t the above is stronger as the incidence tree-width is always smaller t h a n the p r i m a l tree-width plus one [51]. O n e parameter that is used many times i n the literature is hypertree-width a n d s i m i l a r variants w h i c h was first introduced by G o t t l o b et al. [26].  One pa-  rameter that is used m a n y times i n the literature is hypertree-width and similar variants w h i c h was first i n t r o d u c e d b y G o t t l o b et al. [26]. A generalized hypertree decomposition of a h y p e r g r a p h H = (V, E) is a triple ( T , W, A), where (T,W) is a tree-decomposition of the p r i m a l graph of H and A is a f u n c t i o n that assigns t o every vertex t of T a set of edges in E such that W C (J A(i). T h e w i d t h of (T, W, A) t  is the m a x i m u m of |A(t)| over all nodes t of T.  (Generalized) Hypertree-width is  different f r o m tree-width of the p r i m a l graph only in the way we measure the w i d t h of a tree-decomposition: Instead of counting the number of vertices i n a node, we count the number of edges that cover these nodes. T h e generalized hypertree-width of H is the m i n i m u m w i d t h over all its generalized hypertree-decompositions. A hypertree-decomposition (T, W, A) is a generalized hypertree decomposition that satisfies one special condition: (|J X(t))f)X(Ti) t a n d X(T ) t  is  (JseT  t  C W , where T is the subtree rooted at t  t  Ws- T h i s c o n d i t i o n is added for technical reasons to make the  hypertree decomposition computable when it is constant. It is not k n o w n whether  85  generalized hypertree-width is computable i n p o l y n o m i a l time w h e n it is constant. The  hypertree-width of H is defined accordingly. G o t t l o b et al. (See [26] or [25] for a survey) show how a n o p t i m a l hypertree-  decomposition can be c o m p u t e d for a hypergraph w i t h b o u n d e d hypertree-width b y associating i t w i t h certain cops a n d robber games. T h e y also show that the constraint satisfaction problem is solvable i n p o l y n o m i a l time for constant hypertreew i d t h hypergraphs. A constraint satisfaction problem is a set of constraints (Si, Ri) where Si is a tuple of variables from a set of variables X a n d Ri is a list of  j tuples of values from some d o m a i n D. that a l l constraints are satisfied. ((x\,X2,---  ,Xk),R)if  A solution to C S P is a valuation such  A valuation V : X  —• D satisfies constraint  (v(xi), v(x ), • • • , v(xk)) G R- I n this specific m o d e l , a l l pos2  sible valuations of the tuple Si are e x p l i c i t l y given, i.e. are part of the i n p u t , a n d , hence, the number of possible valuations is upper bounded by the i n p u t size. F o r example, i n the S A T i n p u t tp = (a V b V c) A (a V c) A (6 V c) A b, the second clause is represented as  ((a,c),{(T,F),(T,T),(F,F)})  i n this model. T h i s is i n contrast  to a t y p i c a l i n p u t to S A T (and other problems), w h i c h represents the set of values, t h a t satisfy a constraint v i a a f o r m u l a (e.g. (a V c)). I n this m o d e l , if we add a b i g constraint (i.e. Si is big) we can make the problem easier to solve. F o r example, i f a constraint contains a l l the variables, then we can s i m p l y t r y a l l valuations given for t h a t constraint a n d check if one works for the other constraints as well. T h a t ' s basically w h y hypertree-width is related to the time required to solve C S P . A d l e r et a l . [2] prove that hypertree-width is w i t h i n a factor 3 +-e of several other h y p e r g r a p h measures: generalized hypertree-width, (monotone) marshalw i d t h , h y p e r b r a m b l e number, hypertangle number, hyperbranch-width, and hyperlinkedness. 86  5.3  Hyper-D-width  5.3.1 Let  Definition  H = (V, E) be a h y p e r g r a p h . A hyper-D-decomposition of H is a pair (T, W)  where T is a tree a n d W — {W \t'€. V(T)} t  is a f a m i l y o f subsets of V(H)  such that  for every connected set S: . (HI)  T\ := {t\W n S ^ 0} / 0, a n d s  t  (H2) T h e s u b g r a p h of T w i t h vertex set T\s  a n d edges  {(s,t)\W D W n 5 ^ 0} s  t  forms a connected subtree of T . T h e w i d t h of a hyper-D-decomposition (T, W) is the m a x i m u m of \Wt\ — 1 over a l l nodes  t € V ( T ) . T h e hyper-D-width of a h y p e r g r a p h is the m i n i m u m w i d t h  over a l l its hyper-D-decompositions. F o r example, a hyper-D-decomposition w i t h w i d t h two for the h y p e r g r a p h H = ( { 1 , 2 , 3 , 4 } , { { 1 , 2 , 3 } , {1,4}, {2,4}, {3,4}}) is depicted i n F i g . 5.1. It's not h a r d to prove that i t ' s , i n fact, a m i n i m u m w i d t h hyper-D-decomposition.  F i g u r e 5.1: A hyper-D-decomposition w i t h w i d t h two.  87  5.3.2  Basic Properties  H y p e r - D - w i d t h is a generalization of tree-width. O n regular graphs, where every edge has two vertices, hyper-D-decomposition wants the two vertices i n every edge to share a node. T h i s is exactly what any tree-decomposition wants.  Theorem 20. For every undirected graph G, tree-width{G) = hyper-D-width(G). L e t (T, W)  be a hyper-D-decomposition for a h y p e r g r a p h H.  If we make a  regular g r a p h on the vertices of H by connecting two vertices iff they share a node i n T , then the r e s u l t ' w o u l d be a chordal graph w i t h the same tree-width as the w i d t h ofT.  Theorem 21. For every hypergraph H with hyper-D-width w, there exists an undirected chordal graph G with tree-width w such that for any edge e of H with vertex set S, G[S] is connected. H y p e r - D - w i d t h is inspired by D-width on directed graphs.  In fact, every  m i n i m a l strongly connected set i n digraphs is treated as an hyperedge i n the definit i o n of D-width meaning that hyper-D-width is,, i n some sense, a generalization of D-width.  5.3.3  Stability  A l m o s t all existing connectivity measures for hypergraphs are very sensitive to b i g edges, i.e. edges that contains many vertices. (Generalized) Hypertree-width, hyperlinkedness, h y p e r b r a m b l e number, (monotone) marshal-width are all constant w h e n we have an edge that contains all the vertices no matter w h a t the rest of the h y p e r g r a p h structure is. O n the other h a n d , the tree-width of the p r i m a l graph.is always n — 1 for the above example, where n is the number of vertices. 88  W e w o u l d like a connectivity (cyclicity) measure on hypergraphs to behave i n a stable way (as tree-width does for regular graphs): a d d i n g a constant number of vertices or edges shouldn't substantially change the connectivity. A l l the aforementioned measures violate this  stability condition] so do the tree-width of the d u a l  g r a p h and the tree-width of the incidence graph. U n l i k e all the above-mentioned connectivity measures for hypergraphs, hyperD-width is stable. L e t ' s formally define stability first and then prove the stability of hyper-D-width.  Definition 9. A measure defined on hypergraphs is stable if after removing a con-  stant number of vertices (with all edges containing those vertices) or a constant number of edges (defined on existing vertices) the measure decreases by only a constant. Theorem 22. Hyper-D-width is stable. Proof. It's sufficient to show that hyper-D-width changes by a constant when a d d i n g one new vertex or one new edge. A s s u m e we add a new vertex u and a n a r b i t r a r y number of edges containing u t o a h y p e r g r a p h H. L e t (T, W) be an o p t i m a l hyperD-decomposition of H w i t h w i d t h w. Obviously, (T, W),  where W[ = W U {u} t  for every t £ V(T), is a proper hyper-D-decomposition of the new h y p e r g r a p h w i t h width  w + 1. I n case we add a new edge e =  H, (T,W),  where W[ = W U {v } t  x  {i>i,i>2, • • • , Vfc}  for every t 6 V(T),  t o the h y p e r g r a p h  is a proper hyper-D-  decomposition of the new h y p e r g r a p h w i t h w i d t h at most w + 1.  •  In contrast, all the existing alternative measures are unstable.  Theorem 23. (Generalized) Hypertree-width, hyperlinkedness, hyperbramble number, (monotone) marshal-width, (dual, incidence, or primal) tree width are all un89  stable. Proof. It's proven i n [2] that the first four parameters are w i t h i n a constant factor of each other. Hence it suffices to prove hypertree-width and (dual, incidence, primal) tree w i d t h are unstable. L e t if" be a h y p e r g r a p h w i t h big hypertree-width. A d d i n g one edge that contains all the vertices makes the hypertree-width equal to one. T h u s , hypertree-width is unstable. Similarly, the p r i m a l tree w i d t h is unstable. N o w , let i f be a h y p e r g r a p h w i t h small d u a l tree-width.  L e t i f ' be obtained f r o m i f b y  a d d i n g a new vertex u a n d a l l possible edges that contain u (i.e. 2 edges where n n  is the number of vertices). T h e d u a l graph of i f ' has a clique of size 2  n  (all edges  that contain u) w h i c h means it has d u a l tree-width at least 2 — 1, w h i c h shows n  d u a l tree-width is unstable (under removal of vertex u).. A s for the incidence graph suppose i f is a h y p e r g r a p h w i t h small incidence tree-width. W e show that i f ' , as constructed above, has large incidence tree-width. L e t I be the first ^ vertices of i f . T h e number of edges i n i f ' that contain a l l vertices i n I is at least 2 2 w h i c h means the incidence graph of i f ' contains a Kn " ( a c t u a l l y K„ 2' 2 Hence, its tree-width is at least | .  5.3.4  a as well) s u b g r a p h .  2' •  Comparison  In this section we compare hyper-D-width w i t h other existing parameters defined o n hypergraphs, namely, hypertree-width a n d the tree-width of t h e p r i m a l , d u a l , a n d incidence graph.  Theorem 24. For any hypergraph i f , • hyper-D-width(H) < primal  tree-width(H).  • hyper-D-width(H) < incidence tree-width(H). , 90  • hyper-D-width(H) < dual tree-width(H) + 1. Proof. T h e first inequality follows f r o m the fact that every tree-decomposition of the p r i m a l g r a p h is a hyper-D-decomposition. O n the other h a n d , there exist h y pergraphs w i t h p r i m a l tree-width n — 1 and hyper-D-width one (a h y p e r g r a p h w i t h one edge containing a l l the vertices). A s for the incidence tree w i d t h , let (T, W) be a tree-decomposition of the incidence g r a p h . F o r each edge e = {v\, v , • • • , Vk}, replace every occurance of e i n 2  Wt for t G V(T) some t G V(T),  w i t h v\. Since e and v\ share some node of T, i.e. {e, v } x  C'Wt for  the nodes that contain v\ still make a connected subtree. Moreover,  since e shares some node w i t h every v-i, 1 < i < k, the vertices v\ v )  2)  - • • ,Vk make a  connected subtree i n the resulting tree-decomposition. A g a i n , there are hypergraphs w i t h s m a l l hyper-D-width, but large incidence tree-width. A s s u m e H has 2n vertices {1, 2, • • • , 2n} and n edges of the f o r m e$ = {1, 2, • • • , n, n + i] for 1 < i < n. T h e incidence g r a p h has a K  n>n  subgraph (every i is connected to ej for 1 < i, j < n) a n d ,  hence, has tree-width at least n. However, its hyper-D-width is one. Its m i n i m u m w i d t h hyper-D-decomposition is a star w i t h root r containing W containing Wi — {l,i}  = {1} a n d i  th  r  leaf  for 2 < i < In.  A l m o s t the same statement holds when c o m p a r i n g the d u a l tree w i d t h a n d hyper-D-width. G i v e n a tree-decomposition (T, W) w i t h w i d t h w of the d u a l g r a p h of h y p e r g r a p h H, we show how a hyper-D-decomposition of H w i t h w i d t h at most w + 1 c a n be constructed . l  F o r any vertex u G V(H),  a l l edges that contain u  make a clique i n the d u a l graph. Hence, there is some node i n T , say X(u), contains a l l such edges. In the first step, for a l l u G V(H) Wj(u) :  =  WA(U) O { } u  a  n  that  we a d d a leaf l(u) w i t h  d attach it to the node X(u) i n T . N e x t , for every edge  O n regular graphs we can remove the additive constant one in the inequality. 91  e G E(H),  we pick an a r b i t r a r y vertex v 6 e and replace e w i t h v i n every Wt for  £ € V(T). C a l l the resulting decomposition (T',W). vertices of  N o w , (T", W ) contains only  H. W e c l a i m that (T',W) is a hyper-D-decomposition of H. F i r s t , the  new leaves insure that every vertex u G H is contained i n some Wt (in particular, Wj( )) i n T". Second, for any vertex u € H, all nodes £ 6 X " such that it € W ' make u  t  a connected subtree. E v e r y edge e replaced b y u i n creating T ' , forms a connected subtree i n T that contains the node X(u). Hence, these subtrees are connected i n T " and they connect t o the new leaf node l(u). T h i r d , suppose e = { x i , X 2 , • • • ,Xk} is replaced by x i , then  T'\  Xl  C\T'\ ^ 0. In fact, X(XJ) Xj  G T'\Xl n T " ^ . . So the subtrees  corresponding to vertices of e f o r m a connected subtree. A star g r a p h of size n has tree-width one and (by T h e o r e m 20) hyper-D-width one whereas its d u a l graph is a clique a n d , hence, has tree-width n — 1.  •  Corollary 5. The class of bounded hyper-D-width hypergraphs contains the class of bounded (primal, dual, or incidence) hypergraphs. 5.3.5  cops and robber game  In chapter 4 we obtained lower and upper bounds for D-width i n terms of the number of cops that are required t o w i n certain cops/robber game. A n identical definition of cops and robber games under the new definition of connected components enable us to o b t a i n similar results on hypergraphs.  Theorem 25. let h be a hypergraph. 1. Ifk + l cops have a strongly cop-monotone winning strategy on H then H has hyper-D-width at most k.  92  2. IfH has hyper-D-width at most k then k+l cops have a cop-monotone winning strategy on H. In addition, there exist an algorithm for computing the strongly cop-monotonicity of H in time 5.3.6  0(n ). k+2  Applications  In this section we show that there exist polynomial-time a p p r o x i m a t i o n schemes ( P T A S ) for many problems i n c l u d i n g vertex cover, d o m i n a t i n g set, and m u l t i c u t problems on hypergraphs when the hyper-D-width of the i n p u t hypergraph is constant. Let a generic p r o b l e m P be as follows: F i n d a m i n i m u m number o f vertices i n a h y p e r g r a p h that satisfy some constraint C. We are especially interested i n problems P w i t h the following property. (Decomposable Property)Problem P is decomposable i f it satisfies the following c o n d i t i o n . Let i f be a hypergraph. For any subset X of vertices of H, let Ci, C , • • • , C 2  m  be the connected components of H\X.  o n H[d]. T h e n , X U ( D i U D U • • • U D ) 2  m  Let Di be a solution for P  is a solution of P o n H.  T h e decomposable property lets us choose any suitable X, put it i n the solution, break the i n p u t hypergraph into smaller parts, and solve the p r o b l e m on each part independently.  It's easy to verify that multi-cut, d o m i n a t i n g set, and  vertex cover are examples of such problems.  For example, for the vertex cover '  p r o b l e m , i f we choose all vertices i n X then any edge that intersects b o t h Ci and Cj (i 7^ j) is covered. T h e rest is, then, solving the vertex cover p r o b l e m on each Ci separately. N o w , we show how such problems have a P T A S on b o u n d e d hyper-T-width 93  hypergraphs. T h e idea is similar to the technique that C a l i n e s c u et a l . [15] use to find a P T A S for m u l t i c u t o n b o u n d e d tree-width graphs a n d digraphs. L e t (T, B, W) be a hyper-T-decomposition w i t h w i d t h w for the i n p u t h y p e r g r a p h . L e t t €  V(T)  be the bottom-most node such that there exists a n o p t i m a l global s o l u t i o n that contains at least w/e vertices i n the subtree T  t  rooted at t.  If there is no such t  then the o p t i m a l global solution has fewer t h a n w/e vertices. Such a s o l u t i o n c a n be c o m p u t e d i n time 0(n / ). w  e  Otherwise, let optt be the n u m b e r of vertices of a n  o p t i m a l s o l u t i o n i n T . C h o o s i n g a n d removing a l l vertices i n A = Bt U t  t  [J ^ W e  t  e  breaks T into several connected components each having less t h a n w/e vertices of t  the o p t i m a l solution. Hence, the p r o b l e m can be solved by brute force o n a l l these components i n time 0(n ^ ). w  + e). A s s u m e that the rest of the h y p e r g r a p h has o vertices i n  opt + w < opt (l t  Hence, the number of vertices t h a t we pick is at most  e  t  the o p t i m a l solution. A c c o r d i n g to the i n d u c t i o n hypothesis, we c a n find a s o l u t i o n w i t h at most o ( l + e) vertices. Hence, we can solve the p r o b l e m o n H b y choosing at most (1 + e)(opt  t  + o) vertices, y i e l d i n g a (1 + e)-factor a p p r o x i m a t i o n for P . T h e  details of the a l g o r i t h m are shown i n F i g . 5.2. T o complete this section we prove that a l l aforementioned problems are h a r d even o n b o u n d e d hyper-D-width hypergraphs.  Theorem 26. ticut  Proof.  problem  The vertex  cover problem,  are NP-Complete  L e t C\, C , • • • , C 2  m  the dominating  on bounded  set problem,  hyper-D-width  and the  mul-  hypergraphs.  be a S A T p r o b l e m instance over variables x\, x , • • * , x . 2  W e make a h y p e r g r a p h H = (V, E) w i t h vertex set V = Ui<i< {xi,x~i, n  edge set e$ = C j U {u}, for 1 < i < m a n d e  m +  n  Zi} \J{u} a n d  j = { X J , S 7 , Zi}, for 1 < i < n.  We  c l a i m t h a t the S A T p r o b l e m instance is satisfiable iff the h y p e r g r a p h H has a vertex cover of size exactly n. A s s u m e the S A T instance is satisfiable w i t h setting a l l X j ' s  94  Input: A hypergraph H together w i t h an o p t i m a l hyper-D-decomposition (T, W) Output: M i n i m u m number of vertices that satisfy P •/* L e t L e t X = \J >eT W ,. */ foreach t e T d o Let ti, i = 1, 2, • • • , m, be children of t. t  t  t  t  foreach i do find an o p t i m a l solution o. to P of size at most w/e for L  H[X  U  - W ]. t  If no such solution exist then t r y the next t.  end  Let o = UjOj.  Recursively find a (1 + e)-factor a p p r o x i m a t i o n solution d for H\Xt-  Let opt = t  oUdUW . t  end  r e t u r n optt w i t h m i n i m u m size. F i g u r e 5.2: Solving decomposable problem P o n a b o u n d e d hyper-Dw i d t h hypergraph i n a set X to be true and the rest to be false. I n the h y p e r g r a p h let the vertex cover be X U  {x~i\xi  {xi,x~i,Zi}  0 X}. Obviously, every edge of type Q U {u} and every edge of type  is covered a n d the size of the vertex cover is n. O n the other h a n d , let  X be a vertex cover of size at most n. Obviously, it must have picked exactly one vertex from every triple {x{, xi, Zi}, 1 < i < n which is at least n vertices. Moreover, every edge of type Ci U {u} must be covered by some Xi or x~[. i n d, w h i c h makes a satisfiable solution. F i n a l l y , we mention that the hypergraph constructed above has hyper-D-width at most three. M a k e a star w i t h root u a n d every leaf containing {u, Xi,xi, Zi}, for 1 < i < n. It's easy t o prove that the above reduction works for t h e d o m i n a t i n g set p r o b l e m as well. T h e NP-Completeness of the m u l t i c u t p r o b l e m follows from its NP-Completeness o n bounded tree-width graphs proven by C a l i n e s c u et al. [15].  95  •  5.4  Introducing hyper-T-width  A l t h o u g h hyper-D-width has many nice properties and resembles undirected treew i d t h i n a n a t u r a l way, it has one big disadvantage that we haven't resolved yet: We don't know a p o l y n o m i a l time a l g o r i t h m for c o m p u t i n g o p t i m a l or even approximately ( w i t h i n a constant factor) o p t i m a l hyper-D-decompositions for b o u n d e d hyper-D-width hypergraphs. One o p t i o n is to consider a generalization of directed tree-width [34, 35] instead. R e c a l l the following definition from [35].  Definition 10. Let T be a directed tree. For a vertex t and edge e we say e ~ t ift is one of the end points of e. We also say t > e if either t is the head of e or there is a directed path from the head of e to t inT. Definition 11 (Arboreal (pre-)decompositions and directed tree-width).  An arboreal pre decomposition of a digraph G is a tuple (T, B, W) where T is a directed tree with a unique root, and B = {B \t G V(T)} and W = {W |e G E(T)} t  e  are sets of subsets ofV(G) that satisfy: (RI) B is a partition of V(G) into (possibly empty) sets such that B ^ 0 for the r  root r of T, and (R2) If e G E(T), then B\ := \J{B \t > e] is W -normal or empty. t  e  The w i d t h of an arboreal pre-decomposition (T,B,W) is the minimum k such that for all t G V(T),  \Bt U U ~ t ^ e | < k + 1. An arboreal decomposition is a pree  decomposition in which all B are non-empty, and the directed tree-width of a dit  graph G, dtw(G), is the minimal width of all its arboreal decompositions.  96  D-decomposition is, i n fact, a restricted variant of arboreal pre- decomposit i o n . G i v e n a D-decomposition (T, W) of w i d t h IU of a d i g r a p h G, the following is an arboreal pre-decomposition of w i d t h w for G. (T', B', W),  where T' is obtained  f r o m T b y choosing a r a n d o m root and directing all edges away f r o m the root. F o r any edge e = (u, v) -in T " , B' = W v  v  - W  u  and X  e  = Wn v  W. u  A c c o r d i n g t o J o h n s o n et a l . [34] a set S is Z - n o r m a l if every p a t h f r o m a vertex i n S t o another vertex i n S that contains a vertex i n V(G) — S has a vertex i n Z as well. O n the other h a n d , there is no strongly connected component of G\Z that contains vertices f r o m b o t h S and V(D) — S. Inspired b y the above definition, we define hyper-T-width as follows. Definition  1 2 ( H y p e r T - d e c o m p o s i t i o n a n d h y p e r T - w i d t h ) . A hyper T-  decomposition  of a hypergraph H is a tuple (T,B,W)  where T is a directed tree  with a unique root, and B = {Bt\t G V(T)} and W — {W \e G E(T)} are sets of e  subsets ofV(H) that satisfy: (RI) B is a partition of V(H) into possibly empty sets such that B / 0 for the r  root r of T, and (R2) If e G E(T), then B^ := \J{B \t > e} is W -normal or empty. A set S is t  e  Z-normal if there is no connected component of H\Z that contains vertices from both S andV(H) - S. The w i d t h of a hyper T-decomposition (T.B,W)' is the minimum k such that for all t G V(T), \Bt U U ^t W \ < k + 1. The hypef T - w i d t h of a hypergraph H is the e  e  minimal width of all its hyper T-decompositions. In the following section we show that hyper-T-width has a l l the nice p r o p erties of hyper-D-width. It's stable, has the balanced-separator property, and has 97  all currently k n o w n algorithmic advantages of hyper-D-width. I n a d d i t i o n , we can compute an approximate hyper-T-decomposition w h e n hyper-T-width is constant.  5.4.1  Properties  Theorem 27. Hyper-T-width is stable. Proof. It's sufficient to show that hyper-T-width changes by a constant w h e n a d d i n g one new vertex or one new edge. A s s u m e we add a new vertex u and an a r b i t r a r y number of edges containing u t o a hypergraph H.  L e t (T,B,W)  hyper-T-decomposition of H of w i d t h w. Obviously, (T, B', W ) ,  be a n o p t i m a l  where W[ = Wt U  {u} for every t G V(T) and B' = B , when r is not the root and B' — B U {u} for r  r  r  the root r, is a proper hyper-T-decomposition of the new h y p e r g r a p h .  r  Moreover,  (T, B', W') h a d w i d t h 'tu + 1. I n case we add a new edge e = {vi,V2, • • • , ffc} t o the h y p e r g r a p h H, (T, W ' , 73'), where W[ = W li {vi} for every t G V ( T ) , is a proper t  hyper-T-decomposition of the new hypergraph.  •  A s mentioned i n ther earlier section, a hyper-D-decomposition is a restricted version of a hyper-T-decomposition. Hence, Theorem 28. For any hypergraph H, the hyper-T-width of H is less than or equal to its hyper-D-width. Therefore, Theorem 29. The class of bounded hyper-T-width hypergraphs contains the class of bounded (primal, dual, and incidence) hypergraphs. Proof. T h i s is a direct consequence of Theorems  98  24 and 28.  •  A s for algorithmic applications of hyper-T-width we show that a p r o b l e m P that satisfies the decomposable property admits a P T A S on b o u n d e d hyper-T-width hypergraphs. T h e idea is quite similar to hyper-D-width. W e consider the deepest edge e = (r, r') (i.e. r has m a x i m u m depth) such that the s u b g r a p h Be has more t h a n j vertices of some o p t i m a l solution, where w is the hyper-T-width of the i n p u t h y p e r g r a p h a n d e is any constant. N o w a d d i n g all vertices X  e  i n the solution does  not change the number of vertices i n the solution by more t h a n a m u l t i p l i c a t i v e factor 1 + e.  5.4.2  Computation  T h e b i g advantage of hyper-T-width over hyper-D-width is the fact that we can' a p p r o x i m a t e l y compute i t when it is constant.  Johnson et a l . [34] prove this for  directed tree-width a n d their proof generalizes i m m e d i a t e l y t o hypergraphs.  In  p a r t i c u l a r , they introduce the notion of haven order and prove that directed treew i d t h and haven order are w i t h i n a constant factor of each other.  Theorem 30 (Johnson et al. [34]). H{G) - 1 < tree-width{G) < ZH{G) + 1 for digraphs G, where H(G) is the haven order of G. T h e i r proof for tree-width(G) < 3LT(G) + 1 is constructive. If the haven order of G is at most w then i t builds an arboreal decomposition of w i d t h at most 3w+l. I n this section we show that the construction quickly transfers to hypergraphs w i t h o u t any major change. We basically m i m i c the proof of Johnson et al. [34] here. A s our definitions of connectivity and havens are different f r o m theirs, the proof is completely illustrated below. L e t ' s start w i t h defining haven order on hypergraphs. 99  Definition 13 (haven and haven-order). Let H be a hypergraph. A haven of  order k is a function 3 assigning to every set Z C V(H) with \Z\ < k, a connected V(H). and \Y\ < k then 3(Y) C B(X).  component of H \ Z such that ifXCYC  The haven-order of H is the largest k such that H has a haven of order k Theorem 31. H(H) - 1 < hyper-T-width(H) < 3H(H) + 1 for hypergraphs H, where H(H) is the haven order of H. Proof. (Left inequality) L e t (T, W, B) be a hyper-T-decomposition of w i d t h w of H. For any node t let Xt — B U U ~ t W - F h s t observe that w + 1 cops can catch a robber i n the t  e  e  cops/robber game. A s s u m e a hyper-T-decomposition (T, W, B) of G of w i d t h w is given. T h e cops c a n start at XQ = A , where r is the root. L e t r  subtrees of  T w i t h roots ri,r , - • • ,r , children of r. L e t 2  m  T\,T , • • • ,T be 2  m  = (r, ri). A c c o r d i n g to  conditions of hyper-T-decompositions, the robber can only be at vertices i n one of the sets B^.  T h e cops c a n then move to X  Ti  and continue the strategy u n t i l they  t r a p the robber i n one of the leaves. O n the other h a n d if H has a haven of order h then the robber has a w i n n i n g t  strategy against h—1 cops by staying at @(Z), where Z is the set of vertices occupied by the cops. Consequently, H(H) — 1 < hyper-T-width(iJ). (Right inequality) A s s u m e H has no haven of order w. F i r s t , let's prove the following crucial lemma.  Lemma 20. If H has no haven of order w then for every set Y of vertices of H with \Y\ < 2w — 1 there is a subset Z of vertices of H such that \Z\ < w and every connected component of H\Z has at most w — 1 vertices ofY. Proof. A s s u m e not. T h e n for every set Z w i t h \Z\ < w there is one connected 100  component of Z , say 0(Z), such that \B(Z) f l Y\ > w. B u t , this is a contradiction as B is a haven of order w. F o r any Z a n d Z ' w i t h Z C Z ' a n d |Z'| < w, b o t h /3(Z) and /?(Z') contain at least w vertices from Y. A s \Y\ < 2w — 1, we conclude that B(Z') n /3(Z) / 0 w h i c h means B(Z')  C /3(Z)'.  .  •  s Consider a hyper-T-decomposition (T, PF, J5) of H w i t h the following restrictions. 1. F o r any node r, if r is not a leaf then |£? | < w a n d | A | < 3w — 1. r  r  2. F o r any edge e, |W | < 2w — 1. e  3. Subject to the above conditions we take the hyper-T-decomposition that m i n imizes the m a x i m u m of |J5 |, for a l l r's. r  A s the obvious hyper-T-decomposition w i t h one vertex r and B  R  = V(H) sat-  isfies t h e first two conditions, we conclude that there exist a hyper-T-decomposition (T,W,B) satisfying the above three conditions. If there is no leaf w i t h \B \ > r R  then we are done a n d (T, W, B) would have w i d t h at most 3w — 2. Otherwise, take the leaf Y = W. E  r with maximum  ]B \. A s s u m e R  r' is the unique root of r, e = (r',r) a n d  A c c o r d i n g to l e m m a 20 there exist a set ZQ of at most w — 1 vertices of  H such that every connected component of H\ZQ contains at most w — 1 vertices f r o m Y. L e t Z = Z U {u} for some a r b i t r a r y vertex u i n B .  W e b u i l d a new  R  hyper-T-decomposition satisfying the first two conditions, b u t a smaller \B \ w h i c h R  is a contradiction. L e t X\,X2,  ••• ,X  M  m new leaves r i , ^ , - - - ,r  m  each ri).  Set B  N  be the connected components of H[B ]\Z. R  W e create  a n d connect t h e m to r (i.e. create edges from r t o '  = .Xi a n d change B  R  to . Z D B . R  101  F o r the edge  = (r, r,) set  W  ei  = Z U ( y n Xi).  A s \Y nXi\  < 2w - 1 this insures that \W | ei  2. B y the way, A = Z U Y; thus, |A | <3w r  r  T h e . p r o o f that h y p e r - T - w i d t h ( i f )  -1. < 3H(H)  satisfies c o n d i t i o n •  + 1 is constructive and can  be used to o b t a i n an approximate hyper-T-decomposition.  There is at most n  o p t i m i z a t i o n steps d u r i n g w h i c h we find a set Z and add now leaves to the existing hyper-T-decomposition.  F i n d i n g a set Z of size less t h a n w and verifying that  all connected components H\Z t i m e 0(n ). w+2  contain less t h a n w vertices of Y can be done i n  Hence the. t o t a l r u n n i n g time for finding an approximate hyper-T-  decomposition would be  0(n™ ). +3  102  Chapter 6  Conclusions and Research Directions In this thesis we covered problems related to metric embedding a n d tree-width. W e obtained a low d i s t o r t i o n embedding of series-parallel graphs into £\, c o m p u t e d o p t i m a l embeddings between line metrics when the d i s t o r t i o n was small enough, and proposed tree-width-like connectivity measures, D-width, hyper-D-width, a n d hyper-T-width , for digraphs a n d hypergraphs. A s series parallel graphs a n d /c-outerplanar graphs have b o u n d e d tree-width and b o t h are k n o w n to have constant d i s t o r t i o n (for constant k) e m b e d d i n g into £i, b o u n d e d tree-width graphs are conjectured to have b o u n d e d d i s t o r t i o n embedding into £\.  Since a good d i s t o r t i o n embedding into £\ implies g o o d - a p p r o x i m a t i o n  for s e v e ral fundamental problems, such as the sparsest cut a n d m u l t i c u t problems, the s t u d y b o u n d e d tree-width graphs a n d their connection to £\ metrics becomes important. Such a connection between tree-width a n d metric embedding a n d , also, the  103  fact that the s t u d y o n tree-width has found numerous applications i n practice, i n spires people to extend i t to similar class of objects: digraphs and hypergraphs. A m o n g many proposed measures for directed graphs, D-width seems t o be the simplest. A s for hypergraphs, hyper-D-width and hyper-T-width are the first stable- connectivity measures for hypergraphs and are more general t h a n p r i m a l , d u a l , a n d incidence tree-width.  T h e y also have application i n m i n i m u m vertex  cover, m i n i m u m d o m i n a t i n g set, and m u l t i c u t problems.  6.1  £\ metrics  We've proven that the a l g o r i t h m given by G u p t a et al. gives a n embedding w i t h d i s t o r t i o n at most 6.0 for every series parallel graph, but gives d i s t o r t i o n at least 3.0 even for some outerplanar series parallel graphs. A n interesting open p r o b l e m is to close this gap. Some other relevant open problems are m i n i m i z i n g the number of used dimensions (which is exponential w i t h G u p t a et al.'s approach) or embedding higher tree-width graphs (tree-width 3 as the first step) into l\ w i t h bounded distortion.  6.2  Line metrics  W e currently know how to compute an o p t i m a l embedding between two line metrics when the o p t i m a l d i s t o r t i o n is small (less t h a n 13.602) and know it is h a r d to do so w h e n the d i s t o r t i o n is at least n for some constant e [29]. A n open problem is t o e  close this gap a n d , for example, study its hardness when the d i s t o r t i o n is 0 ( l o g n ) . e  A n o t h e r very interesting problem is to look for embeddings that have close t o the o p t i m a l distortion. A l t h o u g h finding a constant-factor a p p r o x i m a t i o n when the  104  o p t i m a l d i s t o r t i o n is at least n is h a r d [29], finding such a n approximate d i s t o r t i o n e  seems t o be a lot (easier for smaller distortions.  6.3  D-width  A very challenging open topic is t o study the connection between D-width and d i rected metrics or directed cut problems. B o u n d e d D-width digraphs a d m i t P T A S for multi-cut • problems (when two vertices are considered separated i f they belong to two different strongly connected components).  C h u z h o y a n d K h a n n a [20] re-  cently proved t h a n the sparsest cut p r o b l e m and the m u l t i c u t p r o b l e m are h a r d t o approximate w i t h i n a factor 2 ( n  l o g l  6n  ) for any constant e even o n directed acyclic  graphs. T h i s is a big negative result that basically says that D-width and directed tree-width are irrelevant to cut problems and directed metrics, b u t still leaves the open p r o b l e m of s t u d y i n g d i g r a p h classes that a d m i t constant-factor approximate solutions for cut problems. O n e other research direction is to explore other a l g o r i t h m i c aspects of Dw i d t h such as its c o m p u t a t i o n w i t h D-width is constant.  6.4  Hyper-D-width  H y p e r - D - w i d t h and hyper-T-width are very new and there exist several open p r o b lems related t o t h e m . A n efficient a l g o r i t h m (showing it is fixed parameter tractable i n particular) for c o m p u t i n g o p t i m a l (or approximate) hyper-D-decompositions for s m a l l hyper-D-width w o u l d be very useful problem. E x p l o r i n g algorithmic aspects of hyper-D-width a n d hyper-T-width is also a very nice research direction. T h e r e are some fundamental problems (such as solving C S P , S A T , and finding N a s h E q u i l i b r i a  105  of certain games) that seem to be relevant to hyper-D-width and hyper-T-width a n d finding those connections is an interesting problem.  106  Bibliography [1] Isolde A d l e r . Directed tree-width examples.  Journal of Combinatorial  The-  ory(Series B), 2007. T o appear. [2] Isolde A d l e r , G e o r g G o t t l o b , and M a r t i n Grohe. Hypertree-width a n d related h y p e r g r a p h invariants. In Stefan Felsner, editor, 2005 European Conference on Combinatorics, DMTCS  Graph Theory and Applications (EuroComb '05), volume A E of  Proceedings, pages 5-10. Discrete M a t h e m a t i c s a n d T h e o r e t i c a l C o m -  puter Science, 2005. [3] M i c h a e l H . A l b e r t a n d M i k e D . ' A t k i n s o n . Simple permutations a n d p a t t e r n restricted permutations. Discrete Mathematics, 300(1-3): 1-15, 2005. [4] A . A n d o n i , M . D e z a , A . G u p t a , P. Indyk, and S. R a s k h o d n i k o v a . Lower bounds for e m b e d d i n g edit distance into normed spaces. ACM-SIAM  In Proceedings of Annual  Symposium on Discrete Algorithm, pages 523-526, P h i l a d e l p h i a ,  P A , U S A , 2003. Society for Industrial and A p p l i e d M a t h e m a t i c s . [5] M i k e A t k i n s o n a n d Derek H o l t o n , editors. Permutation  patterns.  Electronic  J o u r n a l of C o m b i n a t o r i c s , C l e m s o n , S C , 2003. I n c l u d i n g selected papers f r o m the conference held i n Otago, February 10-14, 2003, E l e c t r o n . J . C o m b i n . 9 (2002/03), no. 2.  107  [6] Y . A u m a n n and Y . R a b a n i . A n o(log k) approximate min-cut max-fiow theorem and a p p r o x i m a t i o n a l g o r i t h m . SIAM [7] D . A v i s and M . N e w b o r n .  Journal on Computing, 27, 1998.  O n pop-stacks in.series.  Utilitas  Mathematica,  19:129-140, 1981. [8] M i h a i B a d o i u , J u l i a Chuzhoy, P i o t r Indyk, and Anastasios Sidiropoulos. Lowd i s t o r t i o n embeddings of general metrics into the line. I n Proceedings of Annual ACM  Symposium on Theory of Computing, pages 225-233, N e w Y o r k , N Y ,  U S A , 2005. A C M Press. [9] M i h a i B a d o i u , K e d a r D h a m d h e r e , A n u p a m G u p t a , Y u r i R a b i n o v i c h , H a r a l d Racke, R. R a v i , and Anastasios Sidiropoulos. A p p r o x i m a t i o n algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of Annual ACM-SI AM  Symposium on Discrete Algorithm, pages 119-128, P h i l a d e l -  p h i a , P A , U S A , 2005. Society for Industrial and A p p l i e d M a t h e m a t i c s . [10] D i e t m a r Berwanger, A n u j Dawar, P a u l H u n t e r , and Stephan K r e u t z e r . Dagw i d t h and parity games. In The 23rd International  Symposium on Theoretical  Aspects of Computer Science, pages 524-536, 2006. [11] M i k l o s B o n a .  A survey of stack-sorting disciplines. Electr. J. Comb., on(2),  2002. [12] Prosenjit Bose, J o n a t h a n F. Buss, and A n n a L u b i w .  P a t t e r n m a t c h i n g for  permutations. Inf. Process. Lett, 65(5):277-283, 1998. [13] J . B o u r g a i n . O n lipschitz embeddings of finite metric spaces i n hilbert spaces. Israel Journal of Mathematics, 52:46-52, 1985.  108  [14] W i l l i a m J o h n B r i n k m a n .  Metric Space Emebeddings into l\: An optimization  approach. P h D thesis, P r i n c e t o n University, November 2004. . [15] G r u i a C a l i n e s c u , C r i s t i n a G . Fernandes, a n d B r u c e Reed.  Multicuts in un-  weighted graphs a n d digraphs w i t h b o u n d e d degree a n d b o u n d e d tree-width.  Journal of Algorithms, 48(2):333-359, 2003.. [16] Douglas E. C a r r o l l , A s h i s h G o e l , a n d A d a m Meyerson. E m b e d d i n g b o u n d e d b a n d w i d t h graphs into 11. I i i  The 33rd International Colloquium on Automata,  Languages and Programming, pages 27-37, 2006. [17] N i s h a n t h C h a n d r a n , R y a n M o r i a r t y , R a f a i l Ostrovsky, O m k a n t Pandey, a n d A m i t Sahai. Improved algorithms for o p t i m a l embeddings.  Electronic Collo-  quium on Computational Complexity (ECCC), (TR06-110), 2006. [18] Moses C h a r i k a r , K o n s t a n t i n M a k a r y c h e v , and Y u r y M a k a r y c h e v . D i r e c t e d metrics and directed graph p a r t i t i o n i n g problems. In  Proceedings of Annual ACM-  SIAM Symposium on Discrete Algorithm, pages 51-60, N e w Y o r k , N Y , U S A , 2006. A C M Press. [19] C h a n d r a C h e k u r i , A n u p a m G u p t a , Ilan N e w m a n , Y u r i R a b i n o v i c h , and A l i s t a i r Sinclair. E m b e d d i n g fc-outerplanar graphs into £\. In  . ACM-SIAM  Proceedings of Annual  Symposium on Discrete Algorithm, pages 527-536, P h i l a d e l p h i a ,  P A , U S A , 2003. Society for Industrial a n d A p p l i e d M a t h e m a t i c s . [20] J u l i a C h u z h o y and Sanjeev K h a n n a . P o l y n o m i a l flow-cut gaps a n d hardness of  directed cut problems. I n Proceedings of Annual ACM Symposium on Theory of Computing, N e w Y o r k , N Y , U S A , 2007. A C M Press.  109  [21] D . G . C o r n e i l , H . Lerchs, a n d L. Stewart B u r l i g h a m .  Complement-reducible  graphs. Discrete Applied Math., 3:163-174, 1981. [22] R. Diestel. Graph Theory. Springer, 3rd edition, 2005. [23] S. E v e n a n d A . Itai. Queues, stacks, a n d graphs. In Theory of Machines and Computations, Z. Kohavi and A. Paz, Eds., pages 71-86, New Y o r k , N Y , U S A , 1973. A c a d e m i c Press. • \  [24] M . R. G a r e y and D a v i d S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness.  W . H . Freeman, 1979.  [25] Georg G o t t l o b , M a r t i n Grohe, Nysret M u s l i u , M a r k o Samer, a n d Francesco Scarcello. Hypertree decompositions: Structure, algorithms, a n d applications. In Dieter K r a t s c h , editor, Proceedings of the 31st International  Workshop on  Graph-Theoretic Concepts in Computer Science (WG05), volume 3787 of Lecture Notes in Computer Science, pages 1-15. Springer-Verlag B e r l i n Heidelberg, 2005. [26] G e o r g G o t t l o b , N i c o l a Leone, a n d Francesco Scarcello. Hypertree decompositions a n d tractable queries. Journal of Computer and System Sciences, 209:145, 2002. [27] Georg G o t t l o b , Francesco Scarcello, a n d M a r t h a Sideri. Fixed-parameter c o m plexity i n ai a n d nonmonotonic reasoning. Artif. IntelL, 138(l-2):55-86, 2002: [28] A n u p a m G u p t a , A l i s t a i r Sinclair, Ilan N e w m a n , a n d Y u r i R a b i n o v i c h .  Cuts,  trees and £i-embeddings of graphs. Combinatorica, 24(2):233-269, A p r i l 2004. [29] A l e x a n d e r H a l l a n d C h r i s t o s P a p a d i m i t r i o u . A p p r o x i m a t i n g the distortion. I n APPROX-RANDOM,  pages 111-122, 2005. 110  [30] Roger A . H o r n and Charles R. Johnson.  Matrix analysis. C a m b r i d g e U n i v e r s i t y  Press, N e w Y o r k , N Y , U S A , 1986. [31] P a u l H u n t e r a n d Stephan K r e u t z e r . D i g r a p h measures: K e l l y decompositions, games, a n d orderings. I n  Proceedings of Annual ACM-SIAM  Symposium on  Discrete Algorithm, N e w Y o r k , N Y , U S A , 2007. A C M Press. [32] P a u l H u n t e r and Stephan K r e u t z e r . D i g r a p h measures: K e l l y decompositions,  games, a n d orderings. Theoretical Computer Science, 2007. Submitted. [33] P. Indyk. A l g o r i t h m i c applications of low-distortion geometric embeddings. I n  Proceedings of IEEE Symposium on Foundations of Computer Science, page 10, W a s h i n g t o n , D C , U S A , 2001. I E E E C o m p u t e r Society. [34] T . Johnson, N . R o b e r t s o n , P. D . Seymour, a n d R. T h o m a s . Width.  Directed Tree-  Journal of Combinatorial Theory (Series B), 82:128-154, 2001.  [35] T . Johnson, N . R o b e r t s o n , P. D . Seymour, a n d R. T h o m a s .  Addendum to  " D i r e c t e d T r e e - W i d t h " . manuscript, 2002. [36] C l a i r e K e n y o n , Y u v a l R a b a n i , a n d A l i s t a i r Sinclair. L o w d i s t o r t i o n maps b e -  tween point sets. I n Proceedings of Annual ACM Symposium on Theory of  Computing, pages 272-280, N e w Y o r k , N Y , U S A , 2004. A C M Press. [37] T . K l o k s .  Treewidth, Computation and Approximation. B e r l i n : Springer-  Verlag, 1994.  [38] D o n a l d E. K n u t h . Art of Computer Programming, Volume 1: Fundamental Algorithms. A d d i s o n Wesley Professional, 1973.  I l l  [39] N a t h a n L i n i a l , E r a n L o n d o n , and Y u r i R a b i n o v i c h . T h e geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245, 1995. [40] J a n O b d r l e k . Dag-width: connectivity measure for directed graphs. I n Proceedings of Annual ACM-SIAM  Symposium on Discrete Algorithm, pages 814-821,  N e w Y o r k , N Y , U S A , 2006. A C M Press. [41] H . O k a m u r a and P. D . Seymour.  M u l t i c o m m o d i t y flows i n planar graphs.  Journal of Combinatorial Theory (Series B), 31:75-81, 1981. [42] V a u g h a n R. P r a t t . C o m p u t i n g permutations w i t h double-ended queues, parallel stacks a n d parallel queues.  In Proceedings of Annual ACM Symposium on  Theory of Computing, pages 268-277, N e w Y o r k , N Y , U S A , 1973. A C M Press. [43] Satish R a o . S m a l l d i s t o r t i o n and volume preserving embeddings for planar and euclidean metrics. I n SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry, pages 300-306, N e w Y o r k , N Y , U S A , . 1999. A C M Press. [44] B. Reed. Tree w i d t h and tangles: A new connectivity measure and some applications. Suervey in Combinatorics, 241:87-158, 1997. [45] B. Reed.  I n t r o d u c i n g directed tree w i d t h .  In H . J . B r o e r s m a , U . Faigle,  C . Hoede, and J . L . H u r i n k , editors, Electronic Notes in Discrete  Mathemat-  ics, volume 3. Elsevier, 2000. [46] B. Reed, N . R o b e r t s o n , P. Seymour, and R. T h o m a s .  O n packing directed  circuits. Combinatorica, 16:535-554, 1996. [47] M . A . Safari. D i r e c t e d tree-width. M a s t e r ' s thesis, School of C o m p u t e r Science, U n i v e r s i t y of Waterloo, 2003. 11.2  [48] M o h a m m a d A l i Safari.  D-width:  A more n a t u r a l measure for directed tree  width.. I n J o a n n a Jedrzejowicz a n d A n d r z e j Szepietowsk, editors, Proceedings  30th International Symposium on Mathematical^Foundations of Computer Science, MFCS'05, Lecture Notes in Computer Science, volume 3618, pages 745756, B e r l i n , 2005. Springer-Verlag. [49] James H . Schmerl and W i l l i a m T . Trotter. C r i t i c a l l y indecomposable p a r t i a l l y ordered sets, graphs, tournaments and other binary relational structures.  crete Math., 113(l-3):191-205, 1993: [50] P. Seymour a n d R. T h o m a s . treewidth.  Dis-  •  G r a p h searching, a n d a min-max theorem for  Journal of Combinatorial Theory (Series B), 58:239-257, 1993.  [51] Stefan Szeider. O n fixed-parameter tractable parameterizations of sat. I n  SAT,  pages 188-202, 2003. [52] R o b e r t T a r j a n .  S o r t i n g using networks of queues a n d stacks.  J.  ACM,  19(2):341-346, 1972. [53] D . H . Younger. G r a p h s w i t h interlinked directed circuits. I n Proceedings of the  Mid-west Symposium on Circuit Theory, volume 2, pages X V I 2.1 - X V I 2.7, 1973.  113  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
Germany 35 1
China 28 1
United States 5 0
Japan 3 0
City Views Downloads
Unknown 34 1
Beijing 23 0
Shenzhen 5 1
Ashburn 4 0
Tokyo 3 0
Berlin 1 0
Sunnyvale 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052053/manifest

Comment

Related Items