D-Width, Metric Embedding, and Their Connections by Mohammad A l i Safari M .Math . , University of Waterloo, 2003 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Doctor of Philosophy ' . - in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Computer Science) The University of British Columbia September 2007 © Mohammad A l i Safari, 2007 Abstract Embedding between metric spaces is a very powerful algorithmic tool and lias been used for f inding good approximation algorithms for several problems. In part icular, embedding to an £\ norm has been used as the key step in an approximat ion algo- - r i thm for the sparsest cut problem. The sparsest cut problem, in turn , is the main" • ingredient of many algorithms that have a divide and conquer nature and are used in various fields. Wh i l e every metric is embeddable into l\ w i th distort ion O ( logn ) [13], and -"' the bound 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 th constant distort ion, planar graphs and bounded tree-width --- graphs are conjectured to have constant distort ion in embedding to l\. Bounded- tree-width graphs are one of most general graph classes on which several hard prob- lems are tractable. - ' We study the embedding of series-parallel graphs (or, more generally, graphs w i th 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 Metr i c Embedd ing 1 1.1.1 Important Metr ics 2 1.2 £i Metr ics 3 1.2.1 A n appl icat ion 3 1.3 L ine Metr ics • 8 1.4 Directed Metr ics 10 1.5 Bounded tree-width graphs and digraphs 10 1.5.1 Undirected Tree W i d t h 11 1.5.2 Directed Tree W i d t h 12 1.5.3 Directed tree-width and Directed Metr ics 13 ii i 1.5.4 Hyper-D-width . . . 14 1.6 Organizat ion 15 2 t\ embedding of series-parallel graphs 16 2.1 Introduct ion 16 2.2 Construct ing the embedding 17 2.3 F lat tening 20 • 2.4 Dis tor t ion 9.0 • . 24 2.5 Dis tor t ion 6.0 25 2.6 Lower bound •. 29 2.7 Conclus ion and Future Work 31 2.8 Proof of L e m m a 4 32 3 Embedding between Line Metrics 40 3.1 Introduct ion 40 3.2 Prel iminaries • 42 3.3 Forbidden Permutat ions 44 3.4 Embedd ing between two line metrics 45 3.4.1 A lgor i thm . 45 3.4.2 Largest Eigenvalue 46 3.4.3 Bound ing dk 48 3.5 Comput ing Separabil ity 49 3.6 Pat tern matching for permutations -50 3.7 Sortable Permutations • 53 3.8 Conclusions and Future Work 55 iv 4 D-Width 57 4.1 Introduct ion " . . . 57 4.2 Definit ions . ,. 60 4.2.1 D-width 60 4.2.2 Directed tree-width and haven order 62 4.2.3 Cops and robber game 64 4.3 Directed One Trees 66 4.3.1 A lgor i thmic results '•. 70 4.4 Compar ing D-width and directed tree-width 72 4.4.1 Arb i t ra ry gap between different games 73 4.4.2 A rb i t r a r y gap between D-width, directed tree-width, and haven order 76 4.5 Upper Bounds for D-width . . 78 4.5.1 Comput ing the strongly cop-monotonicity '. . . . 80 4.6 Conclus ion and Future Work 82 5 Hyper-D-width 83 5.1 Introduct ion • 83 5.2 Background 83 5.3 Hyper-D-width 87 5.3.1 Def ini t ion 87 5.3.2 Basic Properties 88 5.3.3 . Stabi l i ty 88 5.3.4 Compar ison 90 5.3.5 cops and robber game 92 .5.3.6 Appl icat ions 93 v 5.4 Introducing hyper -T-width 96 5.4.1 Propert ies 98 5.4.2 Computa t ion ' 99 6 Conclusions and Research Directions 103 6.1 (\ metrics . 104 6.2 L ine metrics • . . 104 6.3 D-width 105 6.4 Hyper-D-width . . . ." 105 Bibliography • • • • 107 v VI List of Tables 3.1 Distor t ion of TTI: for several values of A: - 49 3.2 d,,. 49 v i i List of Figures 2.1 The graph Gx'e for e = ( s 6 , i 6 ) 20 2.2 F la t ten ing a triangle. The right figure is really two degenerate triangles. 21 2.3 A pair of flattened triangles in a triangle sequence from x to an an- cestor edge wi th endpoint y. Consider ing this case provides some intu i t ion for our stronger., parameterized, inequality 26 2.4 Lower bound example 30 3.1 The 4-separable permutat ion (2.4.1,3) 44 3.2 A lgo r i thm . 46 3.3 I l lustrat ion of permutat ion TX\-0 48 3.4 A separation tree 51 3.5 5-sortable permutat ion (:-; indicates coupling) 54 4.1 A digraph (left) w i th its D-decomposition of w id th one (right). . . . 61 4.2 G raph on which 4 cops have a winning strategy but 5 cops are required for robber-monotone strategy 75 4.3 G raph on which 4 cops have a robber-monotone winning strategy but 5 cops are required for cop-monotone strategy 75 4.4 F i nd ing a strongly cop-monotone winning strategy 81 vi i i 5.1 A hyper-D-decomposition wi th w idth two : 87 5.2 Solving decomposable problem P on a bounded hyper-D-width hy- pergraph 95 ix Acknowledgements This thesis and my entire career owes a lot to many people. I want to take the opportuni ty to thank them all for their support and encouragement without which I could not reach where I am. Throughout my P h D I have benefited from invaluable help that I received from my supervisor, Professor W i l l i am Evans. I had regular weekly meetings wi th h im dur ing which I learned a lot from his insightful comments and bri l l iant mind and learned how to discuss scientific problems and how to efficiently do research. W i l l generously shared wi th me his valuable experience in research and helped me do my P h D research. I would like to deeply thank h im for the opportuni ty that I had to have h im as my supervisor. I am grateful to my supervisory committee members, Prof. Dav id K i rk- patrick and Prof. Pavol Hel l , who helped me dur ing the preparat ion of this thesis. I would like to thank Dav id , Pavol, and also the university examiners, Prof. Joel Fr iedman and Prof. R ichard Anstee for carefully reading the dissertation and for their valuable comments for improving it. Before coming to U B C , I studied at the university of Waterloo and at Sharif university of technology. I have learned a lot. by working w i th Prof.. Prabhakar Ragde, A lex Lopez Or t iz , Therese B ied l , Mohammad Ghods i , and J afar Hab ib i and am grateful to them. M y time in U B C couldn't be as successful without having so many great and supportive friends. Thank you A r m i n , A l i reza, Baharak, Bahra in , Hamid , Hossein, Mahsa , M a j i d , Mohsen, Ramin , Reza, Saeid, Yaser, Zahra, and many others whose name is missing for all your help and support. 21 years of continuous studying wouldn't have been possible without the support of my great dad, mom, sisters and brothers. I missed them ever since I came to Canada, but they always supported me by regularly ta lk ing to me on the phone and praying for my success. Last, but definitely not least, one person has given the most effort dur ing these 4 years: my dear wife, Maryam. She made our home a very happy place to "i live and always helped to relieve all of the stresses around me. Th is thesis is dedicated to my parents, brothers, and sisters, to .my dear Maryam, and to my dear Mana , my litt le daughter. C r e d i t s . Parts of chapter 4 are based on an ongoing col laborat ion w i th Pau l Hunter. M O H A M M A D A L I S A F A R I 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 in the literature on relevant topics, and a summary of our results which are fully explained in other chapters of the thesis. 1.1 Metric Embedding A metric M = (X, d) is a set of points X with non-negative distance function, d defined on any pair of points with 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 and y, and d(x, x) = 0, for a l l x 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 In 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 semi-metric. 1 A n embedding from one metric A — (XA,CLA) into another metric B — (XB,OIB) is a mapping / from XA to XB- The expansion of /, denoted by exp(f), is the largest expansion over al l distances, i.e. sup^, y dB^J^l'y-jy^ • The contraction of embedding /, denoted by con(f), is the largest contraction over all distances, i.e. s u p x y dB(?(x)Vf(y)) • distortion of embedding / is defined as exp(f) x con(f). Dur ing the last decade or so, low distort ion embedding between metrics has been used extensively to design efficient approximat ion algorithms. The reason is simple: Some problems P are easily solvable if their input comes from some metric class B but are hard for inputs from some other metric class A. If one can embed an input metric in A to a new metric in B w i th low distort ion and solve P on the new metric and translate the result on the original metric, this usually yields an approximat ion algor i thm for metrics in A- 1:1.1. Important Metrics Some metrics are of part icular interest for researchers because of their role in f inding approximat ion algorithms, or their connection to other interesting problems (see the survey by P io t r Indyk [33 ] ) . Every edge-weighted, undirected graph defines a metric where the points in the metric are vertices in the graph and the distance between two 'points is the shortest path length between the corresponding vertices. Notice that every metric corresponds to a complete graph w i th edge weights equal to the distance between edge end points. Some important metric classes of this type are those derived from planar graphs (that correspond to shortest paths of weighted planar graphs), trees, outer-planar graphs, /c-outer-planar graphs, and bounded tree- width ' graphs. Another type of metric that appears frequently in the l iterature is if metric 2 which is the set of points in M d where for any two points X = (xi,x2, • • •, Xd) a n d Y = 0/i> 2/2, • • • j yd) the distance between them is defined as . \\X- Y\\k =-tf\x! -yi\k + \x2 - V2\k + --- + \xd- yd\k (1.1.) for k — oo, \\X - YWoo = max-fjzi - yi\, \x2 - 2/21, • • • ,\xd~ Vd\}- In part icular, the l\ metric, for its close connection w i th cut problems, the £2 or Eucl idean metric, for its famil iarity, and the £ o o , for its s impl ic i ty of computat ion, are of interest for many researchers. Note that we use £̂ instead of £f when dimension is not a concern. . Embeddings between various important metrics have been studied before. For example, every n-point metric is isometrically embeddable(i.e. w i th distort ion 1) into £00, though w i th many dimensions (O(n)), and is embeddable into the £k metric w i th distort ion O ( ^ ) [13, 39]. 1.2 li Metrics There are several reasons why £\ metrics are important to study. One main reason is their close connection w i th the mult i-commodity flow problem and its dual version, the sparsest cut problem. Whi le the max imum mult i-commodity flow problem is solvable in polynomia l t ime, the sparsest cut problem is known to be.NP-hard [24]. In general, if for any length assignment of edges on a given graph the associated shortest path metric can be embedded into £\ wi th distort ion .a, then the sparsest cut problem'can be solved on that graph wi th approximat ion 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 obta in an 0(logA;) approximat ion for the sparsest cut problem w i th k terminal 3 pairs [6]. Let G = (V, E) be an undirected graph wi th capacities on its edges. Given k terminal pairs ( S J , £ J ) (i = 1,2, ••• ,k), S j , i j e V , and A: rea lva lued demands, derrii, the goal is to find a cut S, a subset of V , that minimizes the value C(S)/dem(S), where C ( 5 ) is the total capacity of edges between S and S — V — S and dem(S) is the total demand of those pairs (si,U) that have one node in S and one in S, i.e. | { s t , t i}ns| = 1. Just like the max imum flow m in imum cut relationship, there is a gener- alized max imum cut problem that corresponds to the sparsest cut problem. In the concurrent flow problem (or demand flow problem) k terminal pairs, (si,£j) for i — 1, 2, • • • ,k, are given each having an associated demand, derrii for the ith- com- modity. The goal is to find the max imum fraction A and concurrently routed flows, while respecting edge capacity constraints, such that the flow corresponding to each commodity is at least A times their demands. One easy way to model this is by considering the flow associated w i th every path between commodity pairs. Let Pi be the set of all paths from Si to £j. Let p\ be the jth path in Pi and j\ be the flow routed through it . The linear program is then as follows. Maximize A subject to <de> Eeep{ Pi < ce Ve (LPl) <<Pi> Hjfi > Xdemi V'i The dual of LP\ is as follows. Minimize Y J e c e ^ e subject to Eeepide ><Pi V(z,j) (LP2) . i , Y^idemifi > 1 • V'i 4 One can view d e ' s as distances on edges. The first set of inequalities means <fi is at most the shortest path value from S{ to t;. A s we better have tpi as large as possible in the second set of inequalities, the above L P reduces to Minimize Y"\ cede ^ e (LP3) YJidemid{si,ti) > 1 V'i where d(si,U) is the shortest distance between Si and i j defined by de's. Equivalent ly we can simplify LP3 as m m , . (1.2) d is a metric on G T){d) where C(d) = Y J e cede and D(d) = Y,i=i-kdemid(si'ti)- Let OPT* be the solution to (LP3) . For any part i t ion (S,V — S) the total ca- pacity of edges between S and V — S is C(S) and there is a total demand of dem(S) for commodit ies that have |{sj,i;} f l S\ = 1. Hence, the max imum fraction of de- mands that can simultaneously be satisfied is at most C(S)/dem(S). Consequently, the m in imum sparsest cut is at least OPT*. Let d be a distance funct ion on the vertices of G such that there exists a set S and for every edge e = {x,y} G EQ, de = d(x,y) = 1 if exactly one of x and y is in S, and is 0, otherwise. Such a distance funct ion d defines a cut metric on the vertices of G. One can write the sparsest cut problem as a linear programming problem as follows. ' • • . E ( x , y ) e E V)d(x,y) C{d) „. m m ' — — = (1.3) d defines a cut-metric 2^iz=i...kdemid(si)ti) D(d) If we relax the condit ion that d defines a cut metric and allow it to be any l\ metric then the answer would be the same because of the following two lemmas. 5 Definition 1. Given m metrics M\ = (X,di), M2 = (A, ĉ ), •••, Mm — (X,dm), their sum, M = M\ + M2 + • • • + Mm is a metric (X, d) such that for any pair (x, y), d(x, y) = YliLi di(x, y). M is a positive weighted sum of metrics Mi, M2, • • • , Mm if there exist positive values w\,W2, • • • ,wm such that d(x,y) = YliLx widi{x,y) for all pairs (x,y). Lemma 1 (Folklore). Every t\ metric can be written as a weighted sum of cut metrics. Proof. Every i\ metric is a sum of line metrics (i.e. l\ metrics) that correspond to each dimension. So, it suffices to prove it for line metrics. Assume that M is a line metric of n one-dimensional points x\, X2, • • • ,xn and x\ < x% < • • • < xn. Let Si be a cut metric in which the distance between points p and q (where p < q ) is one only Hp <'i and q > i and is zero, otherwise. Let a.L = x.i+\ — xi. We cla im that M can be wr i t ten as aiSi. Let p and q be two points and p < q. The distance between points p and q is xq — xv = YJ?=p ai which is equal to their distance in YJj c^Sj. El Lemma 2. For positive real values ai, ai, (5i(i = 1,2, • • • , n), m m — < = * — — * Pi 2^iaiPi Proof. Let A = min* f,. Then , Y \0*04 > A 7^a,;A:- Hence, ^ > A. • '.• ;. Let 8 be an &\ metric that minimizes the value ^|^y over al l £\ metrics. Accord ing to L e m m a 1 we can write 8 as a weighted sum of cut metrics. Let 8 = wi8\ -f- W282 + • • • + wm8m where each c\ is a cut metric and tUj's are al l positive. Hence, C{8) = J2ZiwiC(5i) a n d D(s) = J2ZiwiD(6i)- Therefore, according to L e m m a 2, there exists some index j such that jjfi^ < T$j- Since 8 minimizes the 6 value j£r^ over all l\ metrics (that include cut metrics as well) we conclude that DW) ~ D(S) • Consequently, we can formulate the sparsest cut problem as a min imizat ion problem over t\ metrics as follows. I2(x,y)eEc(x>y)d(x>y) ' n „ m m — - — — r - (1.4) d is an t\ norm- 2_a=i--fc « e m i " ( s i , U) B y Lemmas 1 and 2, the value of (1.4) is equal to (1.3) and a solution to (1.3) can be easily obtained from any solution to (1.4). Let OPT be the answer to the sparsest cut problem. A s mentioned before, OPT> OPT*. Let d* be the corresponding distance funct ion to OPT*. How much does OPT* differ from OPT? Accord ing to Bourgain's theorem [13] d* can be embedded into some l\ metric d+ w i th distort ion O ( l ogn ) . W i thout loss of generality assume that the embedding from d* to d+ has no expansion. So, OPT > OPT* = _ ^°ed*f > ^ Ced* YJdemid*(si,ti) derm d*(si,U > Ecedj . > OPT 0 ( l og n) Y, demid+{sl,tl) 0 ( l og n) Hence, d+ gives an O( logn ) approximation for the m in imum sparsest cut. : Notice that what is important in the above inequality is the max imum con- tract ion of distances d+(si,ti). W i t h a slight modif icat ion to the embedding a l - gor i thm one can use Bourgain 's theorem and make an embedding that is not an expansion and guarantees that the contraction for only terminal vertices is not more than 0(log&:), where k is the number of terminals. So, we can improve the approximat ion factor to 0(log/c). See [6] for more details. 7 In order to improve the approximation factor, one need only improve the distort ion of the embedding into £\. For some graphs, in part icular unit-weight expander graphs, this is not possible and the O( logn ) bound for the distort ion is tight [39]. Several researchers have then tried to f ind better distort ion for various classes of graphs. P lanar graphs and bounded tree-width graphs are two widely known classes that are conjectured to be embeddable into £\ w i th constant dis- tort ion. Rao [43] proves distort ion 0{r3 \/\og n) for any Kr^r minor free class of graphs. Th is yields 0(\/\og n) for planar graphs and bounded tree-width graphs. Outerplanar graphs are a class of graphs that are isometrical ly embeddable into £\. G u p t a et al . [28] show that the distort ion for series-parallel graphs is at most 7 + 4\/3 ~ 13.928. We have improved this value to 6.0 and proved a lower bound 3.0 for the embedding a lgor i thm provided by G u p t a et al. . Later, Chekur i et al. [19] prove that fc-outer planar graphs can be embedded into random trees, and hence into £\, w i th constant distort ion, namely, 0(ck), for some constant c. F inal ly , Ca r ro l et al . [16] recently found a low distort ion embedding into £\ for bounded bandwidth 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 th distances measured using the £\ norm (using any £ k norm, is equivalent). Thus , line metrics are one dimensional versions of £\ metrics (£\)- Because of their s impl ic i ty and their many applications, line metrics are often the target metric for low distort ion embedding. Bado iu et al . [9] consider the problem of embedding a fixed graph metric into the best.l ine metric. Tha t is, the authors choose the posit ion of the points on 1 ' 8 a line to minimize distort ion. For the case that G is unit-weighted and has an opt imal line embedding w i th distort ion c, they propose a 0 ( n 3 c ) time algorithm that finds an embedding wi th distort ion 0 ( c 2 ) . Since they can always find an embedding wi th distort ion 0{n) (in linear time) the best of these two embeddings gives an 0 (y / n)-approx imat ion for the opt imal embedding. For unit-weighted trees, they propose an embedding wi th distort ion 8A\/c log c + 4c where A is some parameter known to be at most c. Th i s yields a distort ion 0 ( n 1 / / 3 ) in general 2 . They also provide an exact a lgor i thm which has running t ime . In case that G is weighted and c = 1 + e < 1.5, they obtain an 0(n2) a lgor i thm that finds an embedding / w i th distort ion 1 + 0(e) . Later on, Bado iu et al.[8] consider the problem of embedding metrics corre- sponding to weighted graphs into the line. Let the m in imum inter-point distance be 1 and the max imum be A . They propose an approximate embedding w i th distor- t ion 0 ( A 3 / 4 c n / 4 ) and c ° W for embedding general weighted graphs and weighted trees^ respectively. For the latter case, they prove that it is hard to approximate the opt ima l embedding by Q(^/n). In all cases, c is the opt imal distort ion. We discuss this result further in Section 3 Kenyon et al . [36] consider the problem of opt imal ly embedding one fixed line metric into another fixed one. Th is problem is different from what we have seen so far in the sense that the target metric is fixed and one only needs to find the right mapping between points in the input and target metrics. Such a problem has applications in shape matching and object recognition. Kenyon et al . propose a dynamic programming based algorithm that computes the opt imal embedding in t ime 0 ( n 1 2 ) in case the distort ion is less than 3 + 2\/2 ~ 5.829. We later describe 20 means a rough approximation of 0 with log factors ignored. For example, n l ogn = 0(n) . 9 a family of dynamic programming algorithms that compute opt imal embeddings in polynomia l t ime provided the distort ion is less than 13.60. The latter result was independently found by Kenyon et al. in an extension of their conference paper and also by Chandran et al. [17]. 1.4 Directed Metrics There are several problems whose underly ing metric is not necessarily symmetric. A t r i v ia l example is opt imizat ion metric problems on directed graphs such as f ind - ing a shortest path. There have been some recent attempts to extend symmetric (undirected) metrics to asymmetric (directed) ones. Inspired by the directed version of cut problems, Char ikar et al . [18] study directed metrics for the first t ime and propose directed invariants of i\ metrics, t\ metrics, and some other metrics and study, their relationship w i th directed cut metrics. 1.5 Bounded tree-width graphs and digraphs Tree-width has many connections to what we have talked about so far. For l\ metr ics , ' i t is conjectured that bounded tree-width graphs are embeddable into t\ wi th constant distort ion. G u p t a et al . [28] show that the distort ion for series-parallel graphs (and, in fact, for al l graphs w i th tree-width 2) is at most 7 + 4a/3 ~ 13.928. Trees, that have tree-width one, are also isometrically embeddable into t\. For the multi-cut p rob lem 3 , Cal inescu et al. [15] provide a polynomia l t ime approximat ion scheme ( PTAS ) for bounded degree and bounded tree-width graphs and digraphs. 3 The 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. 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 The not ion of tree-width is considered as a generalization of trees (trees have tree- w id th 1) and many intractable problems are efficiently solvable on bounded tree- w id th graphs. Examples include Hami l ton ian cycle, graph isomorphism, vertex coloring, and edge coloring. . A tree-decomposition of an 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. For each edge (u, v) € E, there exists some node i of T such that {u, v} C Wj. 3. For- al l nodes i, j, k in T , if j is on the unique path from i to k then Wi Pi C W3. The width of a tree-decomposition (T, W) is the max imum of \Wi\ — 1 over all nodes i of T. The tree-width of G is the m in imum width over all tree-decomposition o f G . Notice that the above conditions can be interpreted as follows. For any connected set S of G, ( G l ) T\s := {t\Wt n S ± 0} ^ 0, and (G2) The subgraph of T wi th vertex set T\s and edges { (s,t )|W s D W t D 5 ^ 0} forms a connected subtree of T . 11 It can be easily shown that it suffices that the conditions G l and G2 be true for only edges and vertices, i.e. min ima l connected sets. A connected set S is min ima 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 Reed et al . [46] proved Youngers's conjecture [53] roughly saying that every directed graph has either a large set of disjoint directed circuits or a smal l set of vertices that cover al l directed circuits. In their paper, they defined a version of well-linked sets for directed graphs and since the size of the largest well-linked set in undirected graphs has close relationship w i th tree-width [45] they suggested that the analogous definit ion of tree-width for directed graphs might be very useful, as pointed out in [44]. We believe that a proper definit ion should ideally measure the global connectivity of a digraph. For example the tree-width of a directed acyclic- g raph (DAG) should be smal l because it has low connectivity. Unfortunate ly finding a definit ion for directed tree-width analogous to the undirected case is not easy, since almost al l concepts related to undirected tree-width behave differently in directed graphs. [For example, the bramble number is equal to the haven order in undirected graphs, while they may differ by a factor of two in directed graphs [48].] There is not an agreed-upon generalization of tree-width for directed graphs. For the first t ime Johnson, Robertson, Seymour, and Thomas[34] gave a formal definit ion of directed tree-decomposition (called arboreal-decomposition in their 'paper) and directed tree-width, and proved some theorems relating directed tree-width and haven order. Other researchers proposed different definitions for 12 the directed tree-width. Safari [47] introduces D-width as an alternative definit ion for directed tree-width and proved some facts to justify his definit ion 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\s := {t\Wt n S + 0} + 0, and (D2) The subgraph of T with vertex set T\s and edges {(s,t)\Ws n Wt n S ^ 0} forms a connected subtree of T. A subset S of vertices of G is strongly connected if G[S] is strongly connected. The wid th 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 Chapter 4 we further extend these results and obta in lower and upper bounds for D-width in terms of certain cops/robber games on digraphs and other parameters defined on digraphs. We also characterize the class of digraphs whose D-width is one. 1.5.3 Directed tree-width and Directed Metrics The fact that bounded treerwidth graphs have a close relation w i th l\ metrics quickly brings to mind that bounded tree-width digraphs might have good connections to directed metrics. Bounded tree-width digraphs are actually known to be connected to cut problems: Calinescu'et al. [15] propose a P T A S for bounded degree, bounded tree-width digraphs for the directed mult icut problem on unit-weighted graphs. A 13 directed mult icut in a digraph is a set of edges (or vertices in the vertex version) whose removal leaves no strongly connected component containing both vertices of a terminal pair (s j , i j ) . 1.5.4 Hyper-D-width The way that D-width is defined suggests that it can be extended to hypergraphs. In a D-decomposition of a digraph G, the subtrees corresponding to vertices of every strongly connected set S must form a connected subtree together. S is, in fact, taken from the set of min ima l connected units of digraph G. If G was undirected then S was any edge or any vertex. In case of hypergraphs, the min ima l connected units are single vertices or hypergraph edges. Let us formally define hyper-D-width. Let H = (V, E) be hypergraph. A hyper-D-decomposition of a H is a pair (T,W) where T is a tree and W = {Wt\t € V (T ) } is a family of subsets of V(H) such that for every connected set e G E(H): (HI) T\e := {t\Wt n e ^ 0} ^ 0, and (H2) The subgraph of T w i th vertex set T\e and edges {(s,t)\Ws f l ^ n e f U } forms a connected subtree of T. The w id th of a hyper-D-decomposition (T, W) is the max imum of \X{\ — 1 over al l nodes i € T. The hyper-D-width of a hypergraph is the m in imum wid th over all its hyper-D-decompositions. Hyper-D-width is useful for solving several hard problems. In part icular, we wi l l show, in Chapter 5, how we can find polynomial-time approximat ion schemes ( PTAS ) for vertex cover, dominat ing set, and mult icut problems on hypergraphs when.the hyper-D-width of the input hypergraph is constant. \< ~ ' 14 Next , for the purpose of computabi l i ty, we introduce another measure, called hyper-T-width, which is slightly different from hyper-D-width, inherits almost al l algorithmic and structura l properties of hyper-D-width, and, in contrast to hyper- D-width, is computable when hyper-T-width is constant. 1.6 Organization In Chapter 2 we go through the details of our results on embedding series parallel graphs into l\ w i th distort ion 6.0. In Chapter 3 we talk about embedding between line metrics and discuss the usage of /c-separable permutations in embedding be- tween fixed line metrics and in other applications. We then move our attention to tree-width on digraphs and hypergraphs. In Chapter 4 we review exist ing results on generalization of tree-width On digraphs. In part icular, we study D-width and characterize the class of digraphs w i th D-width one. We also compare D-width w i th several other parameters defined on digraphs. Next , we generalize tree-width to hypergraphs in Chapter 5 and compare our definit ion, hyper-D-width, w i th other exist ing connectivity measures on hypergraphs. We also find several algorithmic applications of hyper-D-width. We finally introduce hyper-T-width which is sl ightly different from hyper-D-width and has the advantage that it is computable in poly - nomial t ime when hyper-T-width is constant. 15 Chapter 2 r , i\ embedding of series-parallel graphs 2.1 Introduction The £\ metric embedding is of part icular interest for its connection to the sparsest cut problem which, in turn , is the main ingredient of various algorithms that have a-div ide 'and conquer nature [28]. As outl ined in Section 1.2.1, the sparsest cut problem can be interpreted as a min imizat ion problem over t\ metrics. One can solve the problem as a min imizat ion over all shortest path metrics defined on the "underlying graph, by linear programming, and then embed the solut ion into l\. The distort ion incurred by the embedding is essentially the same as the approximat ion factor. In fact, if for any edge weights on a graph G, we can embed the corresponding metric into t\ w i th distort ion c then the sparsest cut could be approximated on G wi th factor c. Whi le every metric is embeddable into t\ w i th distort ion O ( logn ) [13] and the bound is realized by graph metrics for expander graphs [39], for special classes 16 of metrics better bounds exist. G raph metrics for trees and outerplanar graphs are isometrical ly embeddable into t\ [41]. In fact, a shortest path metric corresponding to a graph G is isometrical ly embeddable into i\ if and only if G exclude as a minor [28]. Series-parallel graphs [28] and fc-outerplanar graphs [19] (for constant k) are embeddable into l\ w i th constant distort ion. P lanar graphs and bounded tree- w id th graphs are two widely know classes that are conjectured to be embeddable into l\ w i th constant distort ion. Rao [43] proves distort ion 0(r3y/log n) for any Kr%r minor free class of graphs. Th i s yields distort ion 0(\J\ogn) for planar graphs and bounded tree-width graphs. In this chapter, we prove an upper bound of 6.0 on the distort ion of em- bedding series-parallel graphs into t\. We also prove a lower bound of 3.0 for the embedding a lgor i thm given by G u p t a et al. [28] even when the input metric is iso- metr ical ly embeddable into l\. 2.2 : Constructing the embedding In this section, we outl ine the method that G u p t a et al. [28] use to obta in a constant- distort ion embedding of series-parallel graphs into l\. Series-parallel graphs are often defined in a recursive fashion: A n edge (s,t) is a series-parallel graph wi th terminals s and t. If G\ (resp. G 2 ) is a series-parallel graph, w i th terminals s\ and £1 (resp. s2 and £2) then a series construct ion creates a new series-parallel graph, w i th terminals s\ and t2, by taking the union of G i and G2 and unify ing t\ w i th s2. A parallel construction creates a new series-parallel graph, w i th terminals s\ and t\, by taking the union of G\ and G2, and unify ing si wi th s2 and t\ w i th t2- A n alternative way of constructing series-parallel graphs is more incremental. 17 We start w i th an edge. A t each step, we choose an exist ing edge (s,t) , introduce a new vertex x, and connect it to both s and t by edges (x, s) and (x,t). A t the end of the construct ion, we may remove any subset of edges. Th i s actual ly constructs al l tree-width-2 graphs, which are more general .than series-parallel graphs. A lso we may assume that no edges are removed at the end of the construct ion since we may choose the weight of every removed edge to be infinity. G u p t a et al . use this incremental construction to define an ^-embedding of the graph, which is the embedding that we analyze in this section. Consequently, al l the results in this section apply to tree-width-2 graphs. G u p t a et al.[28] present two fundamental ly different methods for embedding series-parallel graphs into. t\ w i th constant distort ion. The first one, which yields a distort ion factor at most 13.92, recursively computes an ^-embedding as a sum of cut-metrics (See the definit ion in Section 1.2.1). The i r second approach is to represent series-parallel graphs as a probabil ist ic sum of trees and bundles (special series-parallel graphs in which all paths between the two terminals have the same length) w i th distort ion at most 8. Us ing the fact that trees are isometrical ly em- beddable into l\ and bundles are ^i-embeddable. w i th distort ion at most 2, they conclude w i th an ^-embedding wi th distort ion at most 16. We focus on their first approach. They use the incremental construct ion of series-parallel graphs to compute the ^i-embedding as follows: Let fi(x, y) be the shortest path 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 th a single edge (s, t) we set Ji(s, t) = /j,(s, t). Assume that in one step we introduce one vertex x and attach it to the endpoints of an existing edge (s,.t). Let 6 = fi(x,s) + fj,(x,t) - n(s,t) 2 and Ps = n(x,t) - n{x,s) + fj,(s,t) 2/x(s,t) 18 and for every existing vertex y let ji(x,y)=6 + Pap,(s,y) + (l-Pa)ii(t,y). (2.1) F i rs t , fi is isometrical ly embeddable into l\ since it is the sum of a cut metric and two isometrical ly embeddable metrics. Next , to show that /} has low distort ion, it is easy to verify that ft, preserves edge lengths, i.e., for every edge (x,y) € G, p,(x,y) = n(x,y). However if x and y are not adjacent in G, we need to show that p.(x,y) > ii[x,y)/c to prove that the distort ion is at most c. The fact that P{x, y) ^ M ĵ v) follows from \i being a shortest path metric and from every edge length being preserved in the new distance. To show that p,(x,y) > fx(x,y)/c, G u p t a et al. consider two cases based on the ancestor relation between x and y. The ancestor edges of vertex x are the parent edge (s, t) to which x is attached dur ing the incremental construct ion plus al l the ancestor edges of s and t. The i r cases are: Case 1: y lies on an ancestor edge of x. Case. 2: Neither x nor y lies on an ancestor edge of the other. For case 1, which turns.out to determine the distort ion of the embedding, G u p t a et al. use an inductive argument to prove that •.. ,, •A(x,y)> (1"f^"1)M(x,y) for al l-f '€ {\, 1). In part icular, for £ = \/3 — 1 this gives the best bound ( ^ K 2 ^ - 1 ) ~ 1^02- We show that the worst distort ion in case 1 occurs when the sequence of ancestor edges from x to y has a special degenerate 1 form (Lemma 3). Us ing this fact and the proof technique of G u p t a et al., we can show that the distort ion of p, is at most 9.0. However, in order to obtain our result, that the distort ion of jl is at 19 Figure 2.1: The graph Gx>e for e = (s 6 , i 6 ) . most 6.0, we need a more precise inductive argument than the one used by G u p t a et a l . Th i s argument appears in L e m m a 4. We also show, in section 2.6, that the algor i thm of G u p t a et al. produces an l\ metric jj, w i th distort ion at least 3.0 on a family of outer-planar graph metrics; metrics that are known to be isometrically embeddable into l\. 2.3 Flattening For a vertex x and 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 from x to (s,t). Tha t is, (si,ti) is the parent edge of either s$_i or ti-\ depending on whether U — £j_i or Si = Sj_ i respectively. To simpl i fy our definitions, we assume SQ = x and to — h- Note that for every 1 < i < k either £j = ti-i or Sj = Si-\. Let Gx'e be the induced subgraph of G that contains x and {S J , £ J |1 < i < k}. The graph Gx'e is a sequence of edge- weighted triangles. Let L j = = /i (s j_ i ,S i ) , and = / i (^_ i , t j ) . See Figure 2.1. It is important to note that the shortest path between any two vertices i n Gx,e is the same as the shortest path between those two vertices in G. A lso, the definit ion of jl on the (series-parallel) graph Gx,e is the same as p, on the, original graph G restricted to the vertices in Gx'e, as long as the order of construction used in the two definitions is the same. 20 Figure 2.2: F la t ten ing a triangle. The right figure is really two degenerate triangles. A triangle w i th edge lengths a, 6, and c is flat if a = b + c or a = \b — c|. The flattened version, Fx'e, of Gx'e contains two flat triangles for every triangle in Gx'e. If Si ^ Si-\ (and £j = £j_i) then contains the flat triangles ( S J _ I , itj, £j_i) and (si,Ui,ti) where i i j is a new vertex not in G and / X ( S J _ I , Uj) = L ' ~ L l 2 ~ 1 + Q ' , Ai(ui,£j_i) = L ' + Z " 2 " 1 + a ' , Ai(si-i,£i-i) = i i - i , ^(si,Ui) = L ' ~ 1 ~ 2 L ' + a i , and fj.(si}ti) = Li. If £,; ^ £j_i (and Sj = Sj_i ) then F 1 ' 6 contains the flat triangles (£i_i, Vi, s,_i) and (ti,Vi,Si) where i>j is a new vertex not in G and = L i ~ L ^ \ M K ^ - I ) = ^ ± % i ± ^ , v,(si-.x,ti-\) = ^ t - i , n(ti,Vi) = ; and n{si,ti) = Li. For example, see Figure 2.2. The graph F 1 ' 6 is series-parallel and it defines the same graph metric on the vertices of Gx,e as the graph G does. Tha t is, the shortest path distance between any two vertices in Gx,e remains unchanged in Fx'e. We may also construct Fx,e fol lowing the order induced by the construction order of. G w i th Ui added after S ; and before (and vi added between U and £i_i). Us ing this construct ion order, let ftp be the l\ distance obtained by G u p t a et al.'s construction (definition (2.1)) on Fx>e. We first prove that jlp(x,y) < ji(x,y). 21 Lemma 3. For an endpoint y of an ancestor edge e of x, P-F(X,V) < P(x,y). Proof. We prove, by induct ion of the order of addit ion of the vertices, that PF{W, y) < p\(w,y) for every vertex w in Gx>e. If w is an endpoint of e then p,p(w,y) = jl(w,y) = fi(w,y). Otherwise, assume :w — s.;_i and S j _ i / Si (the case w = U-i is similar) . Accord ing to the induct ion hypothesis, jlp(si,y) < jl(si,y) and jJ.F{~ki>y) < p,(ti, y). Let a = L j _ i , b — Li, and c = a^. B y definit ion (2.1) of ftp, for p^ = a ^ b a + c , i2F{si-i,y) = 0+pFpF(ui,y) + (1 -PF)PF{U,V) = ^ - — ? r ^ ~ + pF(si,y^j + (1 ̂ PF)pF(ti,y) . B y definit ion (2.1) of / i , for p = jj.(si-i,y) = —-+pjl(s l,y) + (1 - p)jl{ti,y) Hence, A F ( S » - I , J / ) - p(si-i,y) < (pF-p){P{si,y) - - (1 ~ P F ) ^ | — - < b\pF-p\ - (1-PF)^~—- _ (a — b + c)(b — a + c) (a — 6 + c)(b — a + c) ~ 2(a + 6 + c) 2(a + b + c) = 0 • 22 As G u p t a et al. mention [28], we can view the construct ion of fi as a proba- bi l ist ic process. If we are at a vertex x w i th parent edge (s,t), we accumulate <5 (for the triangle (x,s,t)) and then collapse (move) to either vertex s w i th probabi l i ty Ps or to vertex £ w i th probabi l i ty 1 — Ps. B y repeating this process, we move from x to the edge (sk,tk) and accumulate 8 for some triangles in the sequence. Let P s l be the probabi l i ty that when x moves to the edge (si,U) it moves to Sj and let PI = 1 — Pls. The expected sum of the accumulated <5's plus P^L^ (resp. Pj°Lk) is fi(x, y) if y = tk (resp. y = sk). Define A 1 to be the expected sum of the <5's accumulated over all triangles up to the edge (si , t j ) . So, for example, A 0 = 0. Let A = Ak. Then p.(x, tk) = A + P*Lk and jl{x, sk) = A + PtkLk. As 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 Gx,e (resp. Fx,e). Proof. Let e = (w,y) and L = /j,(w,y). Assume when x collapses to e in Gx'e (resp. Fx'e) it collapses to vertex y w i th probabi l i ty pa (resp. pp) and to w w i th probabi l i ty qG (resp. qp). Accord ing to L e m m a 3, jj,p(x,y) < jl(x,y) and p,p(x,w) < fi(x,w). Hence Ap+qpL = fip(x,y) < fi(x,y) = A+qcL. Similarly, Ap+ppL = jlp(x,w) < jl(x, w) = A + PGL. Hence < A + min{Qc — qF,pG — PF} = A + mm{pp — PG,PG ~ PF} < A . Consequently, p,p(x,y) + Ap < jj,(x, y) + A . • 23 2.4 Distortion 9.0 In this section we show how the flattening lemma (Lemma 3) enables us to use G u p t a et al.'s proof, w i th minor changes, to get a distort ion 9.0 bound for series-parallel graphs. They prove the following three inequalities for any £ G (5,1). (a) If Pi~l > £ then fj,(x, Sj) > £L(X, S i_ i ) + (2f - 1)^. (b) If Ptl> ( then p{x,Si) > A(s,ti_i) + (2£ - l )L i- (c) Otherwise, 1 - £ < P ] " 1 < £ and p,(x, st) + ^ ( A * - A i _ 1 ) > p,(x, Si-i) + a*. The above three inequalities imply P(x,Si) + Y 3 ^ ( A i - A ' _ 1 ) ^ min{/i(x-,s i_i) + (2£ - 1 ) ^ , ^ , ^ - 1 ) + (2£ - l ) L i } (2.2) The left hand side of the inequality, when accumulated over al l values of i, generates a value not more than (1 + -^)p(x, s^). The right hand side is a (2£ — 1) factor of some path from x to Sfc. (At step i we choose either the edge w i th length c*i or the one w i th length Li depending on the min imiz ing argument.) Hence, jl(x,Sk) is at least a factor (2f - 1)/1 + = 0 f f.i(x, sk). Choosing £ = \/3 - 1 to maximize this factor gives a distort ion bound of at most 13.92. G iven flattened triangles, we can improve inequality (2.2) and obtain a better 24 .distortion bound. If a triangle is decreasing, i.e. L j = L j _ i — CVJ, A(x, Si) = A* + PJLi = A i _ 1 + P * " 1 ^ + P J " 1 ^ = A i _ 1 + P t \ U + Q i ) + (Pi-1 - Ptl)*i = / i ( a ; , S i - i ) + ( i ^ - 1 - P r 1 ) a i Similarly, /}(£, Sj) = / t ( x , £ i _ i ) + ( P / - 1 — P * _ 1 ) L j . For a decreasing triangle, P s = 1 in Equat ion (2.1). Thus , the probabi l i ty of a move from S j _ i to £j is 0, which means Pi = pi-1 and A* - A i _ 1 = P ^ W Thus, (a) if P t 1 > | then ji(x, s{) = / i f o t i - i ) + ( P p 1 - P't^U > + (b) otherwise, P t i _ 1 < § and p.(x,Si) + 2(Ai - A i _ 1 ) = jl(x,Si) + 2Pls~lai > jl(x, + ( 3 P * " 1 - P r 1 ) " * > * - I ) + f . Together, these inequalities imply ft(x, Si) + 2(A* - A*" 1 ) > m in S i _ i ) + j , fc(x, t^) + y } • (2-3) If the triangle is increasing, i.e. L j = + a, , then /i(x, si) = p.(x, Si) + ai, which again implies inequality (2.3). Us ing inequality (2.3) in place of (2.2) in G u p t a et al.'s proof gives us distort ion at most 9.0. 2.5 Distortion 6.0 The inductive construction of the graph and equation (2.1) encourage us to express fl(si-i,y) in terms of fi,(si,y) and jj,(ti,y), and to reverse the direction of induct ion used in G u p t a et al.'s proof. A lso , where the above approach derives an inequality based on a single vertex Sj (or, symmetrical ly, i j ) , we find that a parameterized 25 s u X* Figure 2.3: A pair of flattened triangles in a triangle sequence from x to an ancestor edge w i th endpoint y. Consider ing this case provides some intu i t ion for our stronger, parameterized, inequality. inequality based on an average of p,(si,y) and y) leads to a better distort ion bound. The price we pay for using this stronger inequality is a much more com- plicated inductive step. In fact, the details of the proof are five pages of dense mathematics. In this section, we give some intui t ion for the result but leave the details to Section 2.8. Rather than a single flat triangle, consider the pair of triangles in 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) = min{^(s, y) + a + 7, n(t, y) + L + 7 - a} where p= • A n y distort ion inequality of the form fj,(u, y) > c[i(u, y) translates, using the above equations, into an inequality that has contr ibut ion from both s and t: pp(s,y) + (1 -p)ji(t,y) +pj> cmm{/j,(s,y) + a + j,p,(t,y) + L + 7 - a}. 26 B y replacing a w i th the equivalent (1 — p)(L + 7) and moving p*y to the right we obtain: pp(s,y) + (l-p)p(t,y) > c m i n { fj,(s, y) + (1 - p)L + (2 - p - p/c)j, n(t,y)+PL-py(l-l/c)} - W h e n we include a A 1 term on the left, this is very similar to the inequality (2.2) used by G u p t a et al. Notice that we can view 7 as a parameter and obtain al l flattened triangle pairs. The distort ion 6.0 result is based on inequality (2.4) by setting c = | , using A1 w i th coefficient one on the left side and replacing 27 w i th (3. We also add 2/3 min {P s l , P t l } L j to the right side to make the induct ion work. Let p\ — p,(si,y) and fi\ = /z(sj,y) for all i (p\ and [x\ are defined similarly) . . Let A j = A — A 1 , i.e., A j is the expected sum of the 5's accumulated over all triangles start ing from the edge (si,U) up to (sk,tk). The precise form our intu i t ion takes is ¥s((3) = l /3min {/4 + P\U.+ (3{l - 2P*), £ + PIU - PJ0} + 2/3 m in { i » PfiLu and &t(J3) = l / 3 m i n K + P\U - P/./3, M j + P\U + (3(1 - 2P})} + 2/3min {P ; , P\}U. Lemma 4. For flattened triangle sequences, for all 0 .< i < k and all (3 > 0, Proof. See Section 2.8. • Let us derive the corollary that is used in proving that p.. has distort ion at most 6.0. 27 Corollary 2. For flattened triangle sequences from x to an endpoint y of an ancestor edge of x, Proof. Since P ° = 1, A = A n , and /i° + LQ > JJPs = fi(x, y), we have •P°£° + P ° £ ° + A 0 = £(* , y) + A > ¥ ° ( 0 ) = vr,°( 0) > The following theorem shows that G u p t a et al.'s construction produces an ^i-embedding w i th distort ion at most 6.0. Theorem 1. For any two vertices x and y, ji(x,y) > Proof. We have two cases. Case 1: y lies on an ancestor edge of x. In this case, by L e m m a 3 and Corol lary 2, 2fi(x, y) > 2p,p(x, y) > fiF(x, y) + AF > which yields a distort ion of 6.0. Case 2: neither x nor y lies on an ancestor edge of the other. The proof of this case is essentially the same as in G u p t a et al. [28]. If x and y are not ancestors of each other then let (s,t) be the last edge added in the construct ion that is an ancestor edge of x and an ancestor edge of y. If (s,t) separates x and y (i.e. every path from x to y passes through s or t) then p,(x,y) = Ax + AV + (P?P? + P*PV)L where Ax (resp. Ay) is the expected sum of the <5's accumulated over al l triangles start ing from x (resp. y) to the edge (s,t) , Px (resp. Ps) is the probabi l i ty that 28 x (resp. y) collapses to s when it moves to (s,t) (similarly for Px and P?), and L = n(s, t). We know PXP? + PxPy > ± m i n { P f + P j , P* + P t"}. W i thou t loss of generality, suppose Px + P | = m i n { P f + P j 7 , P f + P t y}. So, jl(x, y) = Ax + Ay + (PfP? + IfPV)L px i pV > Ax + Ay -\- s L 2 = A a + /i(a,t) A ^ + A(y,£) 2 2 > rix,t)+li(ytt) Corollaries 1 and 2 6 J - 6 ' If (s, £) doesn't separate x and y then there must be a vertex q whose parent edge is (s,t) w i th (s, q) an ancestor edge of x and ( i , 5 ) an ancestor edge of y. Th is case reduces to the previous case by noting that fi,(x, y) is preserved by reordering the construct ion sequence in such a way that (s, q) becomes a common ancestor edge of x and y. (See G u p t a et al . [28] for details.) Consequently, the distort ion is at most 6.0. • 2.6 Lower bound There are series-parallel graphs that cannot be embedded into t\ wi thout some distort ion. The best lower bound on this distort ion, of which we are aware, is 3/2 and is obtained by showing that any ^i-embedding of the unweighted bipart i te graph K2,n (which is series-parallel) has distort ion at least 3/2 [4]. If we restrict our embeddings to be those produced by G u p t a et al.'s con- struct ion, we can prove a better lower bound. The following theorem shows that there exist outerplanar graphs whose t\ embedding v ia that construction incurs dis- 29 Vn-1 Figure 2.4: Lower bound example tort ion arbi trar i ly close to 3.0, even though 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. Let G be defined as follows. V{G) = {xi : 0 < i < n}u{yi : 1 < i < n—1} and E(G) = {(xi, xi+i) of length 1 : 0 < i < n - 1} U {(xi,yi+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. Every shortest path in G from xo to xn has length n. Assume that the first edge added in the incremental construction is (XQ,XI). The construction order of vertices is fixed once this first edge is added; they are added in increasing order of their index, i.e. (XQ,X\), y\, X2, y2, • •• • Let t ing /Ttj = fi,(xi,xo), we have A n - i + fhi-2 + 1 to = ' o — 30 where po = 0 and pi = 1. Let g, = ptn - §, then 9n = 9n-l + 9n-2 2 where go = 0 and g i = | . Th i s implies that 0 < gn < 2/3 for all n, which means f < M n < f + 2/3or equivalently As n increases, we obtain distort ion arbi trar i ly close to 3.0. If the order of incremental construction starts w i th the edge (XJ,V) for v G {XJ+I,yj+i,Uj-i, Vj}, then either j < n/2 or j > n/2 and the same argument, w i th pi — p(xj,Xj+i) or pi = p(xj,Xj-i), respectively, gives distort ion approaching 3.0 2.7 Conclusion and Future Work In this chapter we provided a careful analysis of G u p t a et al.'s construct ion and obtained an upper bound of 6.0 and a lower bound of 3.0 on the distort ion of embedding series-parallel graphs into l\ using that construction. One might also consider the problem of min imiz ing the dimension of the l\ metric as well as its distort ion. B r i nkman and Char ikar [14] show that embedding certain series-parallel graphs (diamond graphs) into l\ w i th constant distort ion re- quires n^ 1 ) dimensions. Whether low dimensional, constant distort ion embeddings for al l series-parallel graphs can be constructed efficiently is an open problem. A very challenging problem is to embed bounded tree-width graphs into £\ wi th low distort ion and, as a first step, graphs w i th tree-width 3. as n approaches infinity. • 31 2.8 Proof of Lemma 4 For flattened triangle sequences, for all 0 < i < k and all (3 > 0, P ^ + ̂ + A i > m a x { ^ s ( / 3 ) , ^ ( / ? ) } (2.4) Proof, (of L e m m a 4) The proof is by induct ion. We-assume the lemma is true for i, i + 1,.. •, k and show it is true for i — 1. We know A j . when L j = L j _ i + CVJ or L j = L j _ i + /3j A j - i = < p i a i + A j when L j = L j _ i - a,u ^P/A + A j when U = U-X - for Since inequality (2.4) is symmetric in Sj and t j , we may assume without loss of generality, that £j = £j_i which means S j _ i collapses to ( S J , £ J ) . : " The proof relies on four technical lemmas (Lemmas 5, 6, 7, and 8). Case 1: (increasing triangle) L j = L j _ x + ai'. Notice that in this case A j = A j _ i and PI = P s - * s Li Li Li piiii+piti+Ai > ^l(P) (by the induct ion hypothesis) > * r : ( ^ ) (by L e m m a 5). We also need to show that P 1 ' 1 ^ + P ^ t i ' 1 + A i - i > ^ j - 1 ^ ) - 32 UP}'1 > \ or ̂ - l + P l - l L i ^ l < f.Li-1+Pls-1Li^l then < * t _ 1 ( 0 ) for all /?.> 0. In this case P J - 1 ^ - 1 + ^ T ^ - 1 + A i - i > *s _ 1 (0) = *t _ 1 (0) > *t_1(0) for all 8 > 0 and we are done. . Otherwise, P*" 1 < ± and / 4 " 1 + P J _ 1 L i _ i > + P T ^ i - i - Define ^ _ M s ~ M t + ( - P t ~ - P s ) ^ ^ 5 ) Th is is the value of / 3 that maximizes ( / 3 ) b y making the two values in the first r min of ^\(8) equal, i.e., /4 + P\U - PiBi = £ + PtU + B%{\ - 2PI) Note that P * _ i > 0 since p}s~l + P^1 L^i > /Jf1 + P s i _ 1 X l _ i . A l so note that Bi > 0, since (^ + p * L i ) - ( M j + p s i L . i ) Hence • p r v r 1 + v r 1 + A * - i = « + ^ + A * >max{*j ( jBi ) ,* i (0)} ( b y induction) > * j _ 1 ( P i _ i ) ( b y L e m m a 6) 3 3 Case 2: (decreasing triangle) Lt = L j _ i — a.;. In this case Pls = P S L _ 1 , / i * , - 1 = ji\ + O j , = / i* + and A j _ i = A j + P^a;, so p r v r 1 + ^ r ^ r 1 + ^ - i = PM+<*)+piti + ^ = pi& + piti + Ai + 2 P > i > + 2ai) + 2 P s i a i (by induction) > %^(P) (by L e m m a 7). We also need to show that P* - 1 /^ - 1 + P/ - 1 /^ - 1 + A i - i ^ ^ t ^ G 9 ) - I n t h i s case, p r v r 1 + p t l t i ~ l + A i _ i = P X + + A , + 2 P 5 v > ¥t(mzx{Bi, 0}) + 2 P ; a i (by induction) > * j _ 1 ( P i _ i ) (by L e m m a 8) Base Case The only remaining step is to prove the base case. Assume tk = y. We have Hk8 = = Lk and ^ = / i * = 0. Thus , Pkjlk + Pftf + Ak = PkLk and *£(/?) = 1/3min{ A 4 + P / % + (3(1 - 2Pk),rf + PkU - Pk(3) + 2/3mm{Pk,Pk}Lk < l/3PkLk + 2/3PkLk = PkL k- 34 As for the inequality PkjJ.k + PtPt + A f c > ̂ t(P), as mentioned earlier, if Ptk > \ then we are done because Pkfik + Ptkjlk + Ak > tf*(0) = # £ ( 0 ) Otherwise, assume P t f c < ±. It's clear that Bk = ~ p " ) L f c = ̂ L f c and * t f c (P f c ) = 1/3 + P s f e L f c + Bk(l - 2Pk)) + 2/3mm{Pk,Pk}Lk = 1/3 ( P*Lk + 2 P n i p k 2 P " ] L k ) + 2/3PkLk 2Lk(Pk - Pkf s Dk _ pk\2 = P^Lk - 3Pk < PsLk = Pkpk + Pkjlk + Ak The proof is now complete. • Lemma 5. If Li = L j _ ! + oti then for all 8 > 0 : *l(p)>V-l(8). Proof. Notice that since L j = + a j , A j = A j _ i and P* = P, :-i i i - i s - •«• s Li • ¥s(3) = 1/3min{/4 + P t % + 8{l - 2Pls), & + PlsL,L - 1*8} + 2/3mm{Ps:,Pti}Li > 1 / 3 m i n K " 1 + P r ' ^ - i + ̂ (1 - 2Pi), M p 1 + ̂ T % - i - TO + 2/3min {P J , P/ } L i since < A4 = ̂ "'t'^, *i = and P j = P * " 1 ^ ' - > 1/3 m i n K - 1 + i T 1 ^ - ! + 0(1 - 2 P J - 1 ) , M l - 1 + * T ^ . - i - ̂ r V } + 2 / 3 n u n { P J - 1 ) P / - 1 } L i _ i 35 since P*.< P* " 1 = * r i ( / ? ) - • • Recal l the definit ion of Bi from the equation 2.5. Lemma 6. If Li = L j _ i + and P j _ i > 0 then m^{¥t(Bi)^\{0)} >Wt-\B i-ij Proof If Pi < 1/2 then > tfj(O) and * r x ( ^ _ i ) - - I A A ; - 1 +K~ l L i - i+p t - i ( i - 2 P r x ) + 2 / 3 ^ - ^ - 1 ' -1/3(AJ + PtLi + Bi(l- 2PD) - 2/ZPtLi = l / 3 P i _ 1 ( l - 2 P / - 1 ) - l / 3 P l ( l - 2 P t l ) - 2 / 3 a i = l / 3 P i _ 1 ( 2 P ; - 1 - 1) - l / 3 P i ( 2 P i - 1) - 2/3oi = i / a ^ - ^ + ^ i ; 1 - ^ - 1 ^ - ! ) Ps - l / s " ^ t + ^ ' P : ) L l ( 2 P ; - 1) - 2 / 3 ^ •* s 1 i f pi—1- pi—!'> p i < 1 / 3 ^ ^ s ' t ~ 1 ( 2 P ] - x - l ) - l / 3 ^ s 1 ^ 1 + 1 P * 1 ) L i - 1 ( 2 P J - 1) - 2/3a* .s - 2 / 3 a * + l / 3 ( M r 1 - M P 1 + {PI1 ~ P T ^ - i X i - T ^ r ) s P s < - 2 / 3 a , + l / 3 ( 2 P r 1 P . t - i ) ( p i _ ' ) Ps pi—1 _ pi—1 < 0 36 Otherwise, if P\ > 1/2 then * j (0 ) > a n d tr 1^-!)-*^) - i / 3 ( z i r i + p r 1 ^ - i + ^ _ i ( i - 2 P r i ) + 2 / 3 P r -l/3(AJ + P s % ) - 2 / 3 P s % = i /3P i _ 1 ( i -2P t i - i )+2/3 ( p r 1 - p r 1 ) ^ - i = i/s^' 1 - AT1 + (^r1 - ^r1)^-! ( 2 P i - i _ 1 } Ps +2/3(pr1 - p r ^ L i - i < i / 3 ^ - ^ ( 2 P r 1 - i ) + 2 / 3 ( p r 1 - p r 1 ) ^ Ps < 2 / 3 P r 1 L i - i ( 2 - - Jn )+2/3 ( p t i - 1 - pr1)^-! Ps - 2/3 < 0 Lemma 7. 7/ L j = L j _ i — a j £/ien /or all B > 0 . r s (/5 + 2aj) + 2 P > > v & r 1 ^ ) - Proo/. Let /?' = /3 + 2aj . ' * J s(/3') + 2P s la.j = 1/3 min{/4 + P/L, + - 2PJ), ^ + P\L% - P^' } + 2/3min {P ; , P/}L, + 2 P > . • > 1/3 m i n K + PIU + SP^a, + p'(l - 2P*) , /4 + P JL j + 3 P > j - Pls0} + 2/3min {P s \ P^L^ (since 2/3min {P s i , P t ' }L ; + P*a ; = 2/3min{P*, P t l } ( L i - i - a,) + P > ; > 37 2 / 3 m i n { P s i , P / } L i _ i + l/3P*«i > 2/3min { F * , P^ } L i _ i ) = 1/3min{/xr1 + PiU-x - c*i(2 - 4P*) + P'(l - 2PI), + PiU-x + 2 i>i - Pi/3'} + 2/3min{P 5 \ P^L^x since /2* = fi\ + CUJ and L i = L j _ i — - l / S m i n i y - 1 + P r ^ i - i + 0(1 - 2^_1), ^r1+pr1^-! - ̂ r1/?}+2/3 m i n ^ - 1 , p*- 1 }^ since P* = P* 1 and U = £j_i Recal l the definit ion of P j from 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 i } ) > * r 1 ( 5 i - i ) -2P i a i . Proo/. If P i > 0 then %{Bi) = l/3(/4 + P/L, - P/P,) + 2/3min{i* P t J } L , = 1/3 (Vs + P*L, - - + (P t l - Pi)Li^j + 2 / 3 P t % = 1/3 (fi-1 - ai + P / ( L i _ i - - 1/3 ( ^ ( A C * - « i - M P 1 + tf? - Pi)(Li-i - a i ) ) + 2 / 3 ^ ( ^ - 1 - ^ ) 38 since fj, ls = ji\ 1 — a j , L j = L j _ i — a j , and P t l = P/ 1 < 1/2 = n ' \ B ^ ) - 1/3^(1 + 4P< - § ( 1 + P t 1)) •2 = * r 1 ( P j _ 1 ) - 2 P ] a , + l / 3 a j ( 9 P s l - 4 ) + 2 / 3 a j P | - . > tfj-^Bi-i) - 2 P ; a j (since P/ < 1/2). If P i < 0 then /Li» + U < 4 + P\Li and tfj(O) = l/3(/4 + P t % ) + 2/3P/Lj . Since P j - i > 0, P j can't be too negative. In fact, B = f4-j4 + {Pt- pi)Lt _ ̂ T1 - /xj- 1 + (pr1 - pr1)^-! - 2pr iaj p i p i -1 s -1 s 2P}oi 2P\ai = Bi-i B y - > ~ pi * s 1 s Thus, * K 0 ) = l / 3 ( M * + P ^ i ) + 2 / 3 P t % = * j ( P j ) + 1/3P/PJ = ̂ -H ĵ-i) - l / 3 a , ( l + 4 P ; - § ( 1 + P^) + 1/3P/Pj Pi s 2 > ^ ( S i - i ) - l / 3 o i ( l + 4J» - § ( 1 + Pi)) - 2/3a P < pi '• - t /y - / —<• pj = ̂ rĤ i-i) - 2 P > j + l /3a j (9P ; - 4) > WftBi-i) - 2Plsai (since Plt < 1/2). • 39 Chapter 3 Embedding between Line Metrics 3.1 Introduction In this chapter, we focus on comput ing an opt imal embedding between two fixed line metrics. A line metric is a set of points on a real one-dimensional line w i th the distance between any pair of points being their l\ distance (any t\. distance is equivalent for one-dimensional points). As we mentioned earlier, Kenyon et al . [36] consider the problem of opt i - mal ly ; embedding one fixed line metric into another fixed one. They propose a polynomial-time, dynamic programming based, algorithm that computes the opt i - ma l embedding if the distort ion is less than 3 + 2\/2. To this a im; they show that any permutat ion that contains (3,1,4,2) (see F ig . 3.1) as a sub-permutation corre- sponds to an embedding w i th distort ion at least 3 + 2\/2. A l l permutations that do not contain a (3,1,4,2) sub-permutation have a nice structure that allows finding the opt imal such permutat ion using dynamic programming in polynomia l t ime. It 40 is worth mentioning that the problem is recently proven to be NP-hard when the opt ima l distort ion is unrestricted. Ha l l et al. [29] prove that if the opt imal distort ion 5 is at least n £ , for some constant e, then the distort ion is not even approximable w i th a factor <5 1 - e ' , for any e', unless P = N P . In this chapter, we extend the result of Kenyon et al . [36] by considering a less restricted class of permutations called /c-separable permutations. In part icular, we improve the threshold value on distort ion below which an opt imal embedding can be found in polynomia l t ime from 3 + 2^2 to 13.602. We also study several interesting problems related to permutations such as forbidden permutations, pattern matching, and stack sorting. We recently found that Kenyon et al . (in an extension of their conference paper [36]) and Chandran et al . [17] have also extended the 2-separable result to /c-separable permutations. B y considering 9-separable permutations, they obtain a polynomia l t ime dynamic programming solution that works in those cases when the distort ion is less than 5 + 2^/6 ~ 9.90. We obta in (independently) the same result and show that the same technique can be used, by considering larger values of k, to find opt imal embeddings when the distort ion is less than 13.602. We (as well as they) show that the technique does not work for distort ion greater than 13.928 no matter how large k is chosen to be. The structure of this chapter is as follows. After introducing basic definitions, in Section 3.2, we prove, in Section 3.3, that the class of /c-separable permutations have a finite set of forbidden permutations. Then , in Section 3.4, we propose a polynomia l t ime algorithms for embedding between two fixed line metrics provided the opt imal embedding permutat ion is /c-separable. We also study some algorithmic and non-algorithmic related results such as computing separability. Sections 3.6 is : 41 devoted to the problem of finding a /c-separable permutat ion in a text permutat ion. We propose a polynomia l t ime dynamic programming algori thm for the problem. In Section 3.7, we interpret /c-separable permutations in terms of the way they are sortable using a queue. F inal ly , in Section 3.8, we address some open problems related to our work. 3.2 Preliminaries Notice that we can view any embedding as a mapping from source points to destina- t ion points or, simply, as a permutat ion. Assume the opt imal embedding between U and V is the permutat ion TT. We specify a permutat ion IT w i th the notation (vr(l) ,7r(2),-.. ) 7 r (n) ) . Permutat ion 7rn of size n contains permutat ion TT^ of size k, if there exist indices h < h < • • • < h such that for all 1 < i < j < k, iTk(i) < ^k(j) iff Kn{k) < Kn{lj)- In this case, we refer to ir^ as a sub-permutation of 7r n . In part icular, TTnV is the unique permutat ion of size y — x + 1 such that nfi'y(i) < ^n'v{j) iff 7T n(i + 1 - X) < 7T n(j + 1 - X). A nice interval I in ix is either a singleton or is a set of at least two consecutive numbers from 1 to n such that their mapping, v ia TT, is st i l l a set of consecutive numbers. For example, the permutat ion (4,3,1,2) contains several nice intervals: [1,2], [3,4], [2,4] and [1,4]. If the interval [ l ,n] can be decomposed into a constant number of sub- intervals such that each sub-interval is mapped, v ia TT, to a sub-interval in V and this property recursively holds for al l sub-intervals, then we can use dynamic program- ming and find the opt imal embedding. More formally, an interval I is k-separable, wi th respect to ir, if either it has at most k points or it can be part i t ioned into 42 nice sub-intervals h,l2, • • • ,Im (1 < m < k) such that each Ii is /c-separable. TT is /c-separable iff the interval [ l ,n] is /c-separable w i th respect to TT. The separability of TT is the min imum k > 1 such that TT is /c-separable. For example, the permutat ion TT = (2 ,4 ,3 ,6 ,5 ,1 ) is 3-separable. I\ = [1,3], I2 = [4,5], I3 = [6], and it is clear that I\, I2, and I3 are 3-separable as well. Every 3-separable permutat ion is 2-separable, since for any three nice sub- intervals that part i t ion a permutat ion, two may be merged to form a nice sub- interval. Therefore, we don't have any permutat ion w i th separabil ity 3. It's also easy to see that for k > 4, there exist permutations of size k w i th separabil ity k. These permutat ion could be interpreted in a simpler way: they don't have any nice interval except the interval [1, k]. We refer to these special /c-separable permutations as non-separable permutations. The distort ion incurred by a permutat ion TT, denoted by d(jr), is the min i - m u m distort ion incurred by embedding any two line metrics U and V v i a TT. For example, d(?r) for the permutat ion in F ig . 3.1 equals 3 + 2\/2 and happens when [a, b, c, x, y, z] = [1,-^/2,1,1,-^,1]- As we see later, Theorem 5 states that d(7r) equals the largest eigenvalue of a 0-1 matr ix corresponding to TT. Corresponding to every permutat ion TT of size n, there exist three permuta- tions TT°, TT1, and 7 r _ 1 that are similar to TT and incur the same distort ion. For all i's, TT°(i) = n + 1 — 7r(i), 7r1(7r( ,i)) = i, and 7r - 1( ' i ) = n + 1 — vr 1(i). For example, if TT = (2 ,4,1,3) , 7T° — 7T1 = (3,1,4,2) and 7 r _ 1 = TT. Throughout this chapter, we always assume that a permutat ion comes wi th all its four symmetric forms. For example, when we say 2-separable permutations avoid TT = (2,4,1,3) we mean they avoid (3,1,4,2) as well. Let Ll/j be the set of all non-separable permutations of size k. Let dk be the 43 l a 2 b 3 c 4 7T Figure 3.1: The 4-separable permutat ion (2,4,1,3) . m in imum distort ion over all permutations in life. For example, II4 = {(2,4,1,3)}, n 5 = {(2,4,1, 5,3), (2, 5,3,1,4) , (3, 5,1,4,2)}, and it 's not hard to see that d 4 = al*, — 3 + 2\/2. Note that by ir € Tlfc we impl ic i t ly mean v r 0 , ^ 1 , ^ - 1 € 11̂ as well. So, (3,1, 5, 2, 4) is also in II5. 3.3 Forbidden Permutations One commonly asked question regarding many permutat ion classes is whether they can be characterized by a finite forbidden set of permutations or not. For exam- ple, a permutat ion is 2-separable if and only if it contains neither (2,4,1,3) nor (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 n o r nk+2- where n^m is the permutation of size 2m in which TT*(2i)2m — i and 7r*(2i — l)2m — i + m. Alber t and Atk inson [3] (See Theorem 4 in their paper) use the notion simple 44 • ' for non-separable and call Tx\m an exceptional permutat ion. They obtain their result by using some results from Schmerl and Trotter [49] on part ia l ly ordered sets. 3.4 Embedding between two line metrics In this section we prove the following theorem which is a generalization of Kenyon 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 dk+i or there exists an 0(n5k+3) time algorithm for computing the optimal embedding. Recal l that dk+i is the m in imum distort ion over all permutations in Ilfc+i. Let 7r be the opt imal embedding permutat ion. If 7r is not /u-separable then, according to Theorem 3, ir contains either a permutat ion in Tik+i or 7 r £ + 2 (in case that A: is even). d(nl+2) is increasing and one can easily see that d(nl2) — 21.954 1 . Since dk+i < 7 + 4\/3, according to Theorem 6, we conclude that d(ir) > dk+i- Otherwise, if 7r is fc-separable, an algorithm for finding the opt imal embedding follows. 3.4.1 Algorithm If the opt imal embedding ir is /c-separable then we can compute it in t ime 0 ( n 5 f c + 3 ) by a dynamic programming approach. Every sub-problem is a mapping between two sub-intervals I = {u{,Uj+i, • • • , U i + r n - i } and J = {VJ,VJ+\, • • • , ^ + m _ i } that we specify by the tr iple (i, j, m). Moreover, we need to know the mappings of the four boundary points of both intervals for comput ing the distort ion. Thus , each entry 1TX12 = (7,1,8,2,9,3,10,4,11,5,12,6). In fact, it's not had to prove that d(ir^k) = 2k + 2.yjk(k- 1) - 1. 45 i h k i + m-l Figure 3.2: A lgor i thm. in the dynamic programming table corresponds to 7 variables (i, j, m, i\, j i , 32) in which i and j are the start of both sub-intervals, m is the length of sub-intervals, i\ = 7r(z), %2 = 7r(i + m — 1), j i = 7 r _ 1 ( j ) , and 32 = TX~1{J + m — 1). (See F ig . 3.2.) Assume I is part i t ioned into at most k sub-intervals i i , I2, • • • ,Ik such that each Ix is mapped to an interval in J . There are 0 ^ f c _ 1 ) possibil it ies for part i t ioning I into Ix's. There are at most k\ possibilities for Jx's. (We assume that Jx is the mapping of Ix.) We also need to know the mapping for each boundary of Ix's and Jx's which has 0 ( n 4 f c _ 4 ) possibilities. (The mapping for four of the boundary points is already known.) Once we have fixed all the sub-intervals and the mapping for al l boundary points, we can compute the distort ion by using the distort ion corresponding to every sub-interval as well as the expansion and inverse expansion corresponding to single edges between boundaries of consecutive sub-intervals. In tota l , we need to consider 0(n5k~5) cases and it takes O(n) to compute the distort ion for each case. Since our dynamic programming table has 0 ( n 7 ) entries, the total running t ime would be 0 ( n 5 f c + 3 ) . 3.4.2 Largest Eigenvalue Assume the distort ion corresponding to a permutat ion ix of [ l ,n] is A. Tha t means that for any two line metrics of n points each, the distort ion using ix is at least A and 46 there exists a pair of line metrics whose distort ion, using IT, is exactly A. In fact it is not hard to see that the max imum expansion and inverse expansion in embedding U to V happens for a pair of consecutive points, so we need to care only about them. F ind ing d(ir) corresponds to solving a set of linear equations. For example, for the permutat ion in F ig . 3.1, the linear equations are as follows. y + z < x + y + z < y/Xb x + y < y/Xc a + b < y/Xx a + b + c < y/Xy b + c < yfXz or equivalently AX < y/~XX, where A is the adjacency matr ix corresponding to IT and X is [a, b, c, x, y, z]T. In general, for a permutat ion IT of size.n that corresponds to embedding between two line metrics of s ize.n, A has 2n — 2 rows and columns where, for al l 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 in U or V if necessary, the expansion and contraction both equal y/X. Thus, for any single edge in U and V we write an inequality to make sure that its corresponding expansion does not exceed Vx. Since we are interested in min imiz ing A we better make the equality AX = y/XX. Therefore, VX is an eigenvalue of A. It is well know that ([30], Chapter •8.2.) the only eigenvalue whose corresponding eigenvector is positive is the largest 47 Figure 3.3: I l lustrat ion of permutat ion 7T15. eigenvalue. Thus , \/A is the largest eigenvalue of A. Theorem 5. Let An be the 0-1 matrix corresponding to TT and let its largest eigen- value be A. Then, the distortion of TT is exactly A 2 and is obtained when the edge lengths are taken according to the eigenvector corresponding to A. 3.4.3 Bounding dk A l though dk is increasing in k, it remains bounded. Th is is somewhat disappoint ing since if it was unbounded we could imagine an algori thm that finds an opt imal embedding for any two line metrics, no matter how large the opt imal distort ion is, whose running t ime is a funct ion of the distort ion. Theorem 6. For any value k there exists a non-separable permutation irk whose distortion is at most 7 + 4v /3- Proof. Let iTm be the permutat ion on [l,2n] where 7T2n(l) = 2, 7T2n(2n) = 2n — 1, •7T2n(2z) = 2i + 2, and 7i"2n(2i + 1) = 2i — 1, for i = 1, 2, • • • , n — 1. Similarly, 7T2n+i is defined as follows. 7r2n+i W = 7T2?i W> for i — 1, 2, • • • , n — 1, 7T2n+i(2n) = 2n + 1, and 7r2n+i(2n + 1) = 2n — l (See F ig . 3.3). ' ' Set du(2i - l ,2 i ) = 1, dv(2i,2i + 1) = \/3, dv(2i - l ,2 i ) = 2 + \/3, and dy(2i, 2i + 1) = 3 + 2\/3. The distort ion corresponding to this pair of point sets is 7 + 4\/3 which means dk<7 + 4a/3 ~ 13.928. 48 J k 5 7 9 11 13 15 17 19 distort ion 8.352 10.896 1-2.045 12.651 13.007 13.233 13.385 13.492 Table 3.1: Dis tor t ion of TTK for several • values of k. fc 4 6 9 12 15 24 dk 5.828 8.352 9.899 10.896 11.571 12.850 k 30 34 38 42 46 dk 13.131 13.316 13.443 13.534 13.602 Table 3.2: dk. • Table 3.1 shows the exact distort ion of such permutations for smal l values of k. F i nd ing dk for small k's (by comput ing the eigenvalue corresponding to al l permutations in H.̂ and taking the min imum) suggests that df. converges to 7 + 4\/3. Table 3.2 shows the value of dk for different k's. Consequently we improve the result of Kenyon et al . [36] from 3 + 2\/2 ~ 5.828 to 13.602. Theorem 7. There exists a polynomial algorithm for computing the optimal distor- tion embedding between two line metrics, provided the optimal distortion does not exceed 13.602. 3.5 Computing Separability Given a permutat ion TT of size n one can compute its separabil ity by the following greedy a lgor i thm. Init ia l ly set x = 1. F i n d the largest nice interval [x,y] (in case x = 1 don't choose y = n), set x — y + 1, and repeat. Recursively find the opt imal 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. Assume / is the largest nice interval that contains x. Suppose an opt imal algorithm OPT behaves differently; let I\, I2, • • • ,Ik be al l intervals returned by OPT that have non-empty intersection w i th I. Since k > 2, because of the maximal i ty of I, we could take / and Ik — I instead of those k intervals in O P T and get a better or equal separabil ity consistent w i th our greedy algori thm. It is very easy to see that Ik — I is a nice interval. • 3.6 Pattern matching for permutations The question of finding whether a permutat ion contains another permutat ion is of interest for many people because of its applications. It is sometimes called pattern matching in the literature and comes as either a decision or a counting problem: G iven two permutations a and TT decide if a contains TT or count the number of occurances of TT in a. The greedy algorithm for recognizing /c-separable permutations in subsection 3.5 is a similar problem: Given a permutat ion TT, does it avoid all permutations in Ilfe+i U 7 r £ + 2 ? Bose et al. [12] considered recognition of 2-separable permutations and pro- posed an efficient a lgor i thm for both the decision and counting problem. They also show that the general decision problem is NP-Complete and the counting problem is #P-Complete . A n alternative way to recognize non-2-separable graphs, as pointed out in [12], is to consider the corresponding permutat ion graph. It' is not hard to see that a permutat ion is non-2-separable iff its corresponding permutat ion graph is Pi-free, meaning that it does not have any induced path of length four. One can use the linear t ime algori thm in [21] to recognize Pi-free graphs. It doesn't seem 50 Figure 3.4: A separation tree. to us that permutat ion graphs corresponding to /c-separable graphs, for k > 2, have any part icular structure. In proposing the linear time algor i thm, Bose et al. [12] introduce a special ordered binary tree called a separation tree corresponding to a permutat ion 7r of 1 to n w i th the following properties: 1. Leaves are 7r(l),7r(2), • • • ,7r(/c) in order. 2. For 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 permutat ion (3 ,4 ,1 ,2 ,8 ,5 ,6 ,7 ) is depicted in F i g . 3.4. S imi lar ly we can extend the definit ion of separation tree and allow it to be /c-ary instead of binary. The 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 iven a /c-separable permutat ion ir, one can easily bu i ld a /c-separation tree. Assume Ii, I2, • • • , Ik are the k /c-separable nice intervals. Recursively bui ld a k- separation tree for each Ij and then connect the roots of all these k trees to a new root. 51 For the reverse direction, assume a /c-separation tree corresponding to TT is given. It is obvious that the set of numbers in the subtree rooted at the j t h chi ld is actually the j t h /c-separable nice interval. • Bose et al. [12] use the separation tree and obtain a dynamic programming algori thm to decide if any 2-separable permutat ion TT is contained in a (larger) permutat ion a. A recursive problem instance in their approach is given a sub-permutation a' = <T1j of a and any node u, that defines a subtree Tu, of the separation tree associated w i th TT, decide if TTU is contained in a', where TTU is the permutat ion corresponding to Tu. Not surprisingly, we can use a similar dynamic programming approach and compute 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(mnk+'2). Proof. Let M(u,i,j) be the number of matchings of TTU in a' — a1^. To avoid double counting, let's assume that i is used in every matching, i.e for every matching (*i)*2) • • • ,ik), nu(ix) = i, for some x. • Assume that u has k children u\,u-2, • • • ,uk in order of their appearance in TTU, i.e. every element in TTUX is less than every element in TTUX+1, for al l re's. TTU is, in fact, part i t ioned into TTU^S. It can be easily proven that M(u,i,j)= II M(ux,ix,ix+i - 1) (ii,*2,—ifc) x=l,— ,k 52 (Assuming that i\ = i and ik+i = j + 1-) We basically part i t ion a1 — a1'-7 into k ranges [ix,ix+i — 1] (for x = 1, 2, • • • , /c — 1) and compute the number of matchings of each Ui into corresponding sub-permutation of T'. Comput ing M(u,i,j) takes 0 ( n f c _ 1 ) t ime and there are 0 ( m n 2 ) possibilit ies for it, i , j . Thus, a dynamic programming approach takes t ime 0(mnk+l) to compute M(u,i,j) for all values of u, i , and j. F inal ly , the value J2i=i • •• n^(uo>hn) equals the number of matchings of 7T into T , where ito is the root of the corresponding separation tree. One can easily augment the algor i thm to output the actual matching or list all the possible matchings as well. • 3.7 Sortable Permutations Another interesting topic related to permutations is characterizing classes of per- mutat ions in terms of whether they' are sortable using tools like stacks and queues. The simplest versions of this problem were studied by Knuth[38] who imag- ined the elements of a permutat ion being an input sequence to a stack. A sequence of push and pop operations results in an output sequence (the popped elements) and the question is what input permutat ion can be sorted (yield an ordered output sequence). Tarjan[52], Even and Itai[23], and Pratt[42] generalized the model to allow mult iple stacks and queues. The answer to the simplest case is known: Single stack sortable permutations can be recognized in linear t ime, are characterized by the forbidden permutat ion . [2,3,1], and there are (2")/(^ + 1) (the nth Cata lan number) of them of length n. Other researchers have studied variations of stacks: Av i s and Newborn[7] considered a less powerful stack called pop-stack in which P U S H operations are as usual, but P O P operations, called MPOP, pop the entire stack. They provide enumeration 53 2 6 7 3 1 5 4 /, = <5} 2 6 7' /, =12},;., = {U,7} I, = {4} 3 1 4 — 5 /:, = (3},;„ = {l} !y f, = (4;5} 1 — 2 — 3 — 4 — 5 — 6 7 Figure 3.5: 5-sortable permutat ion ('-' indicates coupling) answers when we use unl imited pop-stacks or we use a fixed number of pop-stacks in series. Bose et al.[12] also interpreted 2-separable permutations as sortable permu- tations by the following device. The permutat ion is original ly on a queue; each t ime 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. For other related results like parallel-stack sortable permutations the reader is referred to [5] or [11]. Here we give an interpretation of /c-separable permutations in terms of sort- ing. G iven a permutat ion 7r on a queue, we are allowed to do the following opera- tions: • Each t ime we can pick up to k consecutive ranges I\, I2, • • • , Ik of elements of 7T/. and sort them. Once we do so, The entire sub-range I\ U I2 U • • • U h gets coupled and remains coupled forever. • We are not allowed to pick a port ion of a coupled range, however, we can reverse the order of elements in a coupled range. Let 's call- the above sorting mechanism k-sorting. A 5-sortable permutat ion is shown in 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 in 1 to n, for if not we won't be able to insert any element in a coupled range any more. Tha 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 which is equivalent,to fc-separable permutations according to Theorem 9. The other direction of the proof is simple. G iven any /c-separable permutat ion 7r, one can consider its separation tree and sort the permutat ion in a bottom-up fashion. W h e n we. are at a node u, al l its children are already sorted; since it has at most k chi ldren, we can swap the orderings of children to get a sorted permutat ion corresponding to the sub-tree rooted at u. • 3.8 Conclusions and Future Work We considered the problem of f inding a m in imum distort ion embedding of one fixed line metric into another fixed line metric. A s a consequence, we studied properties of permutations under 'certain separabil ity constraints, and discovered features of these permutations in various contexts: forbidden permutations, metric embedding, pattern matching, and stack sorting. The main open question that we would like to address is whether or not we can st i l l find a parameterized solution for embedding two fixed line metrics. Notice that the problem is NP-hard [29] when the distort ion is at least n e , for some constant e, but is unresolved for smaller values of distort ion. A l though we proved that the idea of considering /c-separable permutations does 55 not apply when the opt imal distort ion is greater than 13.602, there is st i l l some hope. One may consider a different class of permutations that are algorithmical ly useful. Another important fact is that we are considering al l permutations whereas only a few of them are a candidate to be an opt imal embedding. It seems to us that excluding permutations that cannot be an opt imal embedding from the set of ^-separable permutations would be a major improvement to our work. Another interesting problem is to look for parameterized approximate solu- tions. It appears that if we allow the opt imal distort ion to be approximated, we can easily avoid many permutations and only look for simple (possibly A:-separable for smal l k) permutations. 56 Chapter 4 D - W i d t h 4.1 Introduction One of the most significant recent advances in the field of algorithmics comes from the G r a p h Minors project of Robertson and Seymour. In addit ion to being a major addi t ion to the structure theory of graphs, the tools developed dur ing their work imp ly algorithmic results such as every minor-closed graph property can be decided in . po lynomia l t ime. The most far-reaching algorithmic contr ibut ion is the intro- duct ion of graph decompositions such as tree decompositions and measures such as tree-width, which have helped identify large classes of tractable instances of hard (e.g. NP-complete) graph problems. The key to the algorithmic success of tree decompositions is that they are readily extendable to arbitrary relational structures. B y considering tree decompo- sitions of the background (or primal) graph, large classes of tractable instances of hard problems can be found for various structures inc luding hypergraphs and d i - rected graphs. The main drawback of this approach is that often information 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. Thus efficient solutions to problems like Hami l ton ic i ty cannot be found by this technique. In [34], Johnson et al. attempted to rectify this (and address problems in directed graph structure theory) by introducing directed tree-width, a generaliza- t ion of tree-width to directed graphs. A l though they managed to demonstrate the algorithmic benefits of arboreal decompositions by providing efficient algorithms for problems such as Hami l tonic i ty and disjoint paths, their measure was awkwardly de- fined and not as well behaved as tree-width, making it difficult to extend to further results. Consequently, other measures such as D-width [48], DAG-w id th [10, 40], and Ke l ly-width [31] have been introduced in an effort to find a more practical generalization of tree-width to directed graphs. A lso in [34], Johnson et. al . introduced a graph searching game to par- t ia l ly characterize directed tree-width. The game, similar to one that Seymour and Thomas used to characterize tree-width [50], involves a robber who can run arb i - t rar i ly fast in strongly connected components, and a set of cops who attempt to capture the robber by blocking his escape routes and landing on. h im. Johnson et al. show that if G has directed tree-width k — 1 then k cops can capture the robber in this game, and towards a converse, if k cops can capture the robber on G, then G has directed tree-width at most 3k — 2. In addit ion, they show that the num- ber of cops required to capture a robber cop-monotonely (i.e. vacated vertices are. never revisited by cops) is different from the number of cops required to capture a robber without this restrict ion, and if k cops have a winning strategy, then 3k — 1 cops have a robber-monotone (i.e. the set of vertices the robber can reach is non- increasing) winning strategy. Adler [1] further extended these results by showing 58 that robber-monotone and robber-non-monotone cop numbers do not coincide, and 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 tree- w id th is cr i t ical to the importance of tree-width as a measure of graph complexity. O n one hand, the game is a good indicator of structural properties of graphs. For example, acyclic graphs only require 2 cops to capture the robber, and the number of cops required does not increase under taking of minors. O n the other hand, the equivalence of monotone and non-monotone strategies implies that the number of cops required can be efficiently computed. W i thout a clean correspondence w i th such games, it is difficult to establish similar results for directed tree-width, part icular ly 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 th D-width one. We then study the game characterization of D-width and show that D-width is bounded above and below by the number of cops required in certain versions of the cop-monotone game. In part icular, we obtain a non-trivial upper bound for D-width which is computable in polynomia l t ime when that bound is constant. We also compare various parameters and show that there exist arbitrar i ly big gaps between haven order, directed tree-width, and D-width. The chapter is organized as follows. In Section 4.2 we formal ly 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. Then , in Section 4.5 we compare D-width w i th other parameters such as haven order and directed tree- 59 width . In the f inal section, we obtain a non-trivial upper bound for D-width and propose an algor i thm for comput ing that bound provided the bound is constant. 4.2 Definitions In this chapter we assume al l graphs are finite and directed unless otherwise stated. We use standard graph theory terminology, see for example [22]. 4.2.1 D - w i d t h We recall the definit ion of D-width as defined in [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 di- rected 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\s:={teT\Wtr\S^$}^%,and (D2) The subgraph ofT with vertex setT\s and edges {e = (s,t) G T\WsnWtr\S / 0} forms a connected subtree of T. On the other hand, an edge is included only if both its end points contain same vertex u of S. The w id th 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 Figure 4.1 shows a digraph wi th D-width one, together w i th an opt imal D- decomposit ion. One can verify the above condit ion for all strongly connected sets: {a}, {&}, {c}, {d}, {e}, {a,b,c}\ {a,c,d,e}, {a,b,c,d}, and {a,b,c,d,e}. a b c d •< e Figure 4.1: A digraph (left) w i th its D-decomposition of w id th one (right). A s D-decomposition is quite similar to tree-decomposition, it inherits all its structura l properties that can be used for algorithmic purposes. For example, similar to the undirected variant [37], if a digraph has a D-decomposition of w id th w, then it has a nice D-decomposition of w id th 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 chi ld j then |Wj — Wj \ = 1. Otherwise, if it has two children j and k then W i = Wj = Wk. In addit ion a digraph G w i th D-width w has a related undirected chordal graph G' w i th 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. Let (T, W) be a D-decomposition of G = (V, E) of w id th w. Let G' = (V, E') where E' = {(u,v)\3t s.t. u G Wt and v G Wt}. In other words, every set of vertices Wt is a clique in G'. (T, W) is a tree-decomposition of G'. Moreover, every strongly connected set in G is a connected set in 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. The proof is essentially similar to the undirected version. G iven a D- decom- posit ion T of G w i th w idth w, let i be the deepest node (pick an arbitrary node as the root) such that the sub-tree rooted at i has at least vertices from W. It's clear that every strongly connected component of D\Wi has then at most ^ vertices from W. • 4.2.2 Directed tree-width and haven order Here we introduce some relevant notation from [34]. G iven two disjoint subsets Z and S of vertices of a digraph G, we say S is Z-normal if every directed path which starts and finishes in S is either wholly contained in S or contains a vertex in Z. A lso , given a directed tree T w i th edges oriented away from 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 path from r to t, and e ~ t if e is incident w i th t. The following concepts were introduced in [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 Br ^ 0 for the root r of T, and 62 (R2) Ife G E(T), then Be := |J{73 t|r > e} is We-normal or empty. The w id th of an arboreal pre-decomposition (T,B,W) is'the minimum k-such that for all t G V(T), \Bt U U e ~ t ^ e l < k + 1. An arboreal decomposit ion is a pre- decomposition in which all Bt are non-empty, and the directed tree-width of a di- graph G, dtw(G), is the minimal width of all its arboreal decompositions. If, in addit ion, 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 in G from B^- to B^ we cal l the decomposit ion good. In [35], Johnson et al . c la im that an arboreal pre- decomposit ion can be transformed into a good one w i th the same width , but this does not follow from their results and remains an open problem. The importance of this problem, and indeed the motivat ion for [35], arises from the fact that the algorithmic results of [34] require a good arboreal decomposit ion. However, the decomposit ion constructed in the proof of Theorem 3.3 of [34] is good, imply ing ' that their algorithmic results do hold. Our second definit ion is motivated by a similar definit ion in [50]. D e f i n i t i o n 6 ( ( P r e - ) h a v e n a n d h a v e n - w i d t h ) . Let G be a digraph. A pre- haven of order k is a function 3 assigning to every set Z C V(G) with \Z\ < k, a union of strongly connected components of G\Z 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 which intersect 3{Y). A haven is a pre-haven such that B(Z) is a single strongly connected component of G\Z for all Z C V(G) with \Z\ < k. The haven-width of G, hw(G), is the largest k such that G has a haven of order k 63 In [50] it was shown that if an undirected graph G has a pre-haven of order k then it has a haven of order k. The analogous question for directed graphs remains an open problem. 4.2.3 Cops and robber game We recall the definit ion of the cops and robber game defined in [34]. The game is played on a directed graph G, by two players: one control l ing a set of k cops [k is a parameter of the game), the other control l ing a visible robber. The cops and the robber occupy vertices in the graph. A move consists of the cop player announcing the next location of the cops and then proceeding to move the cops to this locat ion. Dur ing this, the robber can run at great speed along directed paths which do not contain any cops not being moved provided there is also a cop-free directed path back to his original start ing posit ion. In other words, the robber may move to 'any vertex in the same strongly connected component of G \ X where X is the set of locations occupied by stationary cops. If a cop lands on the posit ion of the robber then the cop player wins, otherwise, if the robber is able to evade capture indefinitely, the robber player wins. More formally, the game consists of positions (X,R) where X C V(G), \X\ < k and R is either empty, or a strongly connected component of G \ X. Init ia l ly the cop player chooses X$ C V(G). w i th |Arj| < k and the robber player chooses a strongly connected component RQ of G \ X to give the in i t ia l position,-(XQ,RQ). If R ^ 0, a move, from posit ion (X,R), consists of the cop player choosing X' C V(G) w i th \X'\ < k and the robber player choosing R', a strongly connected component of G \ X' such that R and R' are contained in' the same strongly connected component of G \ (X D X'). If at any point the robber is unable to choose such a strongly connected component, then R' — 0. Th i s 64 gives the next posit ion (X',R'). A play is a (possibly infinite) sequence of moves, and it is winning for the cop player if it is finite and has a final posit ion (X, 0) for some X, .otherwise it is winning for the robber. A play (XQ, RQ), (X\, R\),... is cop-monotone if the cops never revisit a vertex, that is for all h,i,j w i th h <i < j, Xh f l Xj C Xi. The play is robber-monotone if Ri D Ri+i for all i. For any digraph G, we denote the m in imum number of cops that are required to capture the robber w i th a cop-monotone (resp. robber-monotone) strategy by cop-monotone(G) (resp. robber-monotone{G)). As is usual for these types of games, we are pr imar i ly concerned wi th w in - n ing strategies. A (k-cop) strategy for the cop player is a tuple (Yo, TT) consisting of set Yo C V(G) w i th |Y 0| < k together w i th a function vr : T(V{G)) x V(V(G)) -+ V(V(G)), such that for X C V ( G ) w i th \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 (X0,Ro),(X1,R1),... is consistent w i th a strategy (Yb,7r) if Xo = Yo and X j + i = it(Xi,Ri) for al l i , and a strategy is winning (cop-monotone, robber-monotone) if all consistent plays are winning 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 t ime or the cops are l ifted and placed in separate moves are all equivalent in that the existence of a winning strategy for a given number of cops does not depend on the variant. For the results we present in the following sections, we introduce the idea of a strategy forest. F i x G and k, and consider the directed graph wi th nodes labeled by positions in the cops and robber game, and an edge from (X,R) to (X',R') if such a transit ion is possible under the rules specified above. Tha t is, if R / 0, and either R' = 0 or R and i ? ' a r e in the same strongly connected component of 65 G \ (X n X'). We cal l this the positional graph defined by G and k. A strategy a = (YQ,TT) w i l l define a subgraph IT^ of this graph, consisting of all roots of the form (Y0, R), and edges ((X, R), (X',R')) if X' = n(X, R). We also remove all edges of the form (X, 0). If a is a winning robber-monotone strategy, 11^ takes a very simple form. Lemma 11. If a — (YO,TT) is a winning robber-monotone strategy, then Ua is a forest of rooted trees, with each root having a label of the form (Yo, -)• Proof. Since a is a winning strategy, Ha is acyclic and all its roots are of the form (Yo, _). To show that it is a forest, we need only show that no node has more than one predecessor. Suppose (X',R') has two predecessors. These two predecessors either have a common ancestor (X, R) w i th two dist inct chi ldren (TT(X, R),RI) and (n(X, R), R2) or are descended from two distinct roots (Yo,R\) and ( Y o , ^ ) such that i ? i n i ? 2 7^ 0- (By robber-monotonicity, the non-empty i ? ' i s a subset of i ? i D i ? 2 - ) Bu t R\ and R2 are strongly connected components of G \ rr(X, R) (or G \ Yo), so R\ = R2, contradict ing the distinctness of the nodes. • We call Ilfj the strategy forest associated.with a. 4.3 Directed One Trees Current ly there is no known polyt ime recognition algor i thm for bounded D-width digraphs. For the special case that D-width is one, however, there is a fast recogni- t ion algor i thm based on a structural characterization of such digraphs. Moreover, we prove that directed tree-width and D-width coincide in this case. Th is result is achieved by comparing both measures to the haven order. " . 66 F i rs t , we prove the following theorem relating haven order and 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 in against two cops by staying at B(X) where X is the posit ion of cops. Hence, by Theorem 17, G must have D-width at least two. Since this is not the case, G has haven order at most two. Bu t , the haven order of G cannot be one because G has a cycle (otherwise its D-width would be zero) and, thus, G has haven order at least two. (Simply set /3(0). = C and let B({x}) be a strongly connected component the contains a vertex of C — {x}, where C is a cycle in G.) Consequently G has haven order exactly two. Next , we show if G has haven order two then its D-width is one. It suffices to prove this for strongly connected G since if G has haven order two and D-width d, it contains a strongly connected component w i th haven order two and D-width d. The proof is by induct ion on the number of vertices of G. B y L e m m a 12, G contains a vertex u w i th out-degree (or in-degree) one. Suppose u has out-degree one (the in-degree one case is handled similarly) w i th edge (u, v) being its only outgoing edge. Contract the edge (u, v), by removing u and connecting al l u's incoming edges to v (and ignoring loops if created), to obtain a new digraph G'. B y L e m m a 13, G' has haven order at most, two and, according to the induct ion hypothesis, has D-width at most one 1 . Let T' be a D-decomposition of G' w i th w id th at most one. A d d a new node r to T" w i th Wr = {u, v} and attach it to a node of T" that contains v. It is easy to verify that the resulting D-decomposition is a proper one for G and has D-width one because if S is a strongly connected set in 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 in 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 from a vertex in another component of G \ {u} to a vertex in C. S imi lar ly we say a component C is a u-leaf if there is no edge from C to any other component. Let rootleaf(u) be the m in imum size over al l 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 th 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 contradic- t ion. Let u be the vertex w i th m in imum rootleaf(u) and Cu be the component that minimizes rootleaf('u), i.e. \CU\ = rootleaf(u). Assume, without loss of generality, that Cu is a u-root component. Notice that such components do exist as the graph whose vertices are strongly connected components of G\{u} and whose edges are {(A,B)\3u G A,3v G B s.t. (u,v) G G} is acyclic. It's roots are -u-roots and its leaves are u-leaves. Let /3(x) 2, for any single vertex x, be the strongly connected component of G7\{x} that contains Cu, if x $ Cu, and the strongly connected component of G\{x} 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 both in Cu, then both B(x) and B(y) have vertex u in common. Similarly, if both 2 I nwhat follows we use 3{x) for 0({x}). 68 are in G \ Cu, then both B(x) and B(y) share Cu. For the final G Cu and y G G \ Cu, it suffices to show that B(x) contains at least one vertex from Cu. Let S\, S2, • • • Sk be the. strongly connected components of G\{x} that contain at least one vertex from Cu, in topological order. (At least one such component must exist because \CU\ > 2.) I f any Si contains u then we're done. Otherwise, each Si contains only vertices from Cu because every path from v G G \ Cu to a vertex in Cu contains u (a consequence of Cu being a u-root). Thus , \Si\ < \CU\. We show that some 'Si is an x-root or x-leaf component. Th i s is a contradict ion since Cu is supposedly the smallest such component. For al l y G Cu\ {x}, there exists a path from u to y that contains only vertices in Cu \ {x} (in part icular, that doesn't contain x). If not, then the first component Si (smallest i) that contains such a y is an x-root, a contradict ion. Since Cu is a ix-root and x G Cu, for al l z G G \ Cu, there exists a path from z to u that doesn't contain x. Hence Sk cannot have an outgoing edge (y,z) to a vertex z G G\Cu, otherwise y, z, and u would be strongly connected v ia paths that don't contain x. Th is implies that Sk is an x-leaf, a contradict ion. • 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. Note: The same statement regarding directed tree-width of G and G' was noted by Johnson et al . [34]. Proof. Let B' be a haven of order w for G'. We construct a haven, 8, of order w for G. F i rs t , assume u has out-degree one. For any subset Z of vertices in G, if u E Z, let U(Z) = (Z- {u}) U {v}, otherwise let U(Z) = Z. For Z w i th \Z\ < w, 69 let 3(Z) be the strongly connected component of G that contains 3'(U(Z)). (Note: \U(Z)\ < \Z\ so 3'(U(Z)) is defined.) If C is a strongly connected component of G' \ Z for some Z and u £ Z then either C or C U {it} is a strongly connected component of G\Z. Thus , 3{Z) equals either 3'(U{Z)) or / 3 ' ( [ / ( Z ) ) U { i x } . Therefore, for any two subsets Z\ C Z2 of less than i« vertices of G, XJ(Z\) C XJ{Z2\ so /3(Zx) D/3(Z 2 ) D /3'(C/(Zi)) n 3'(U(Z2)) = 3'{U{Z2)) # 0. Thus , 3{Z2) C /3(Zi). Notice that if C i and C2 are two strongly connected componets of G\Z\ and G\Z2, respectively, then either C2 C C i or C i D C 2 = -0. The case when v has in-degree one is similar. • Corollary 3. The three statements "G has D-width one", aG has directed tree-width one", and "G has haven order two" are equivalent. Proof. Th i s follows from 12 and the following two theorems from [34] and [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 The nice property of directed one-trees is that they have a contractible edge as per L e m m a 12. We can use this property to design recursive algorithms for certain problems on directed one-trees. In the following algorithms, we assume that the contractible edge is (it, v) (with u having out-degree one). We contract the edge by removing u and con- 70 necting all it's incoming edges to v. The case when u has iri-degree one is handled analogously. Recognition To find a D-decomposition w i th w id th one, if it exists, in a digraph G: 0. If G is a single vertex return a single node containing the vertex. 1. F i n d a contractible edge (u,v), contract it, and obtain a new digraph G'. If no contractible edge exists then FA I L . 2. Recursively find a D-decomposition T' for G'. 3. Look for a node of T' that contains v, and add a new node r to it w i th Wr = {u, v} If we keep the list of vertices ordered by in-degree and also by out-degree, we can perform steps 1, 2, and 3 in 0(n) t ime. Thus, the total running t ime is 0 ( n 2 ) . Hamiltonian cycle To find a Hami l ton ian cycle, if it exists, in a directed one-tree G in 0 ( n 2 ) t ime: 0. If G is a single vertex return the vertex. If G is acyclic then FA I L . 1. F i n d a contractible edge (u,v), contract it, and obtain a new digraph G'. Also remove al l edges (x, v) in G' where (x, v) is an edge in G. If no contractible edge exists then F A I L . 2. Recursively find a Hami l ton ian cycle C in G'. 3. Replace the edge (x,v) in C w i th (x,u),(u,v) to obta in a Hami l ton ian cycle for G'. 71 4.4 Comparing D-width and directed tree-width It is conjectured in [48] that D-width and directed tree-width are equal. We disprove this conjecture in this section and prove that there is an arbitrar i ly gap between D- w id th and directed tree-width, though it is st i l l unknown whether the two are w i th in a constant factor of each other. We wi l l also provide several inequivalence results for other relevant parameters such as haven order. To this a im, 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) Let a = (YQ,TT) be a cop-monotone winning strategy, then we c la im a is a robber- monotone winning strategy. Assume not; we show the robber can defeat a by moving to a vacated vertex, contradict ing the assumption that a is winning. Let p = (XQ, RQ), (X\, Ri),... be a play consistent w i th a such that Ri J72 Ri+l for some i. F rom the definit ion of a play, it follows there exists r 6 R4+1 such that r E Xi\ Xi+i. Let p' = (X0, R'Q), (X[, R'x),... be a play consistent w i th a that agrees w i th p up to (X j+ i , Ri+i), such that r G R'j for al l j > i. Note that since r G Ri+i and a is cop-monotone, such a play exists as there wi l l always be a strongly connected component containing r. Bu t then this play is not winning for the cop player. 72 cop-monotone(G) < D-width(G) Assume a D-decomposition (T, W) of G of w id th k. is given. Let T be rooted at a node r. The cops can start at XQ = WR. Let T\,T2, • • • ,Tm be subtrees of T wi th roots r\,r2, • • • ,rm, chi ldren of r. Let Ui be the union of the sets Wj over al l nodes j in T;. Accord ing to conditions of D-decompositions, the robber can only be at vertices in one of the sets U. The cops can move to WTi and continue the strategy unt i l they trap the robber in one of the leaves. The connectivity condit ion of D-decompositions ensures that this strategy wi l l be strongly cop-monotone. • 4.4.1 Arbi trary gap between different games We first observe that there can be an arbitrar i ly big gap between the number of cops required to win by using different strategies in the cop/robber game. Theorem 16. For any m G N there exists: 1. A digraph on which 4m cops can capture a robber, but 5m cops are required to capture it with a robber-monotone strategy. 2. A digraph on which 4m cops can. capture a robber with a robber-monotone strategy, but 5m cops are required to capture it with a cop-monotone strategy. Before we prove Theorem 16, we need to introduce the notion of lexicographic product. Definition 7. Let G and H be digraphs. The lexicographic product , 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)}. The proof relies on the following result, similar to one presented in [32]. 73 Lemma 14. Let G be a digraph, Km 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 • Km. Proof. If k cops have a winning strategy on G, then a winning strategy for mk cops on G • Km is obtained by simulat ing the game on G. If the robber's posit ion is (r, s) E V(G • Km) then we posit ion a robber on r E V(G). We then consider the cops' play on G and play on G • Km by placing n cops on {{x,y)\y E V(Km)} whenever a cop would be placed on x E V(G). It's easy to verify that the cop- monotonic i ty 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 • Km. Aga in we simulate the game for G • Km on G, but this t ime from the robber's perspective. We place a cop on x E V(G) only if al l vertices in V(G • Km) of the form (x,y), y E V(Km) are occupied. B y the pigeon-hole principle, this requires at most k — 1 cops on G. The robber's current posit ion is projected as before. The robber's response r' on G is l ifted to G • Km by playing to a non-occupied vertex of the form (r',y). A s r' is unoccupied in the simulated game, at least one such vertex exists. A s the robber can defeat k — 1 cops on G, the strategy is winning. To complete the proof we need to show that if a strategy is not (cop-monotone, robber-monotone) on G then its corresponding strategy on G • Km is not (cop-monotone, robber-monotone respectively) either. The idea is that if the robbers play according to the above strategy then the cops either need to occupy all vertices of type (x,r), for any x, in G • Km or none of them. Par t ia l l y f i l l ing these vertices doesn't impose any constraint on the robber's movement and, hence, is not useful. It's now very easy to verify that if such a 74 Figure 4.2: G r aph on which 4 cops have a winning strategy but 5 cops are required for robber-monotone strategy. F igure 4.3: G r aph on which 4 cops have a robber-monotone winning strategy but 5 cops are required for cop-monotone strategy. strategy is (cop-monotone, robber-monotone) on G • Krn then it's corresponding strategy on G is (cop-monotone, robber-monotone respectively). • We now tu rn to the proof of Theorem 16. Proof. In [1] it was shown that 4 cops have a winning strategy on the graph in F igure 4.2, but 5 cops are required to capture the robber w i th a robber-monotone strategy. In [34] it was observed that 4 cops have a robber-monotone winning strategy on the graph in F igure 4.3, but 5 cops are required to capture the robber w i th a cop-monotone strategy. The results then follow by tak ing the lexicographic product of these graphs w i th Km, the complete graph on m vertices. • 75 4.4.2 Arbi trary gap between D-width, directed tree-width, and haven order Theorems 15 and 16 immediately yield an arbitrary big gap between directed tree- wid th and D-width. In this section we study the behavior of D-width, directed tree-width and haven order under lexicographic product and independently prove the existence of an arbitrary big gap for the above three parameters. We first prove that D-width behaves well under lexicographic product. Lemma 15. If G is a digraph, and Km the complete graph on rn vertices, then 1 + D-width{G • Km) = m • (1 + D-width(G)). Proof. One can view G»Km as making a clique {u\, u2, • • • , um} out of every vertex u of G and connecting Ui to VJ if and only if (u,v) G E(G). Let (T,W) be a D- decomposit ion of w id th w of G. We construct a D-decomposition (T, W') of G»Km as follows. W is a family of subsets of vertices of G • Km such that for any j and i, Uj G W[ if and only if u 6 W{. It can be easily proven that (T, W) is a proper D-decomposition of G • Km and has w id th m(w + 1) — 1. For the reverse direction, let (T',W') be a D-decomposition of G • Km of w idth w' such that Y2ieT< *s minimized. We 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,u2, • • • ,um}. Proof. A s U is a clique in G • Krn, there must be a node j w i th U C W j . Let % be the furthest node from j that violates the above condit ion, i.e. there are up, uq G U wi th Up G W[ and uq G" W[. Let k be the node before i in the unique path from j to i in T ' . We c la im that dropping u p from W[ st i l l leaves a proper D-decomposition contradict ing the assumption that YlieT' 1^71 ^s m in imum. If not, there must be a 76 strongly connected set S such that vertices of S do not make a connected subtree in the new D-decomposition (obtained by dropping up from W(). Th i s is possible only if 5 Pi W[ D W'k = {up} and there are some vertices of S other than up in W[. Bu t , then, the strongly connected set (S U {up})\{uq} does not make a connected subtree in the original D-decomposition. A s i is the furthest node from j w i th 0 < \U f l W(\ < m, i is a leaf of the subtree that contains up (if a further node 1 contained up then \W[ D U\ = m and thus uq E W[ so T"| U ( J is not connected) and, hence, dropping up from W'L does not violate conditions (D\) and (-D2) for T'\Up. • Now, given a D-decomposition w i th the above property we can replace every node that contains all vertices of U by u and obtain a D-decomposition of G w i th w id th - 1. • m ' A similar result holds for haven-width: Lemma 16. If G is a digraph, and Km the complete graph on m vertices, then hw(G • Km) = m • hw(G). Proof For this proof we define a function / : T(V(G»Km)) -* V{V{G)) by f{X') = {v\(v,k) E X' for al l k E V(Krn)}. F i rs t we show that if. G • Km has a haven, 8, of order mk then G has a haven, 8', of order k. We define 8' as 8'(X) = J{8{X x V{Km))). Now as 8(X x V(Km))f](X x V(Km)) = 0, every vertex (x,y) E 8(X x V(Km)) has x £ X. Bu t then, since 8(X x V(Krn)) is a strongly connected component (maximal strongly connected set), {x} x V(Km) C 8(X x V(Km)) for each such x, so /3'(X) is non-empty and strongly connected. B y observing that if XQY then f(X) C / (Y ) , we see that B'(X) 5 ^ ' (y ) whenever XQY. 77 For the converse, we show that if G has a haven, 8, of order k then G • Km has a haven, /?', of order mk. For this we define B'{X) = (3(f(X)) x V ( i v m ) ) \ X . B y the pigeon-hole principle, if |X | < mk then |/ (X) | < k, so 8' is well-defined on sets X w i th < m/c. Since 8 is a haven, 8(f{X)) is non-empty and disjoint f rom f(X). Thus B(f(X)) x V^i^m) has elements (x',y) such if (x,y) G X , there exists .z G V ( i f m ) such that (x,z) $ X. Thus 8'(X) is non-empty and strongly connected. Aga in , the monotonicity of / implies B'(X) 2 8'{Y) whenever X CY. • Unfortunately, directed tree-width is not obviously so well behaved. However, by replacing vertices in an arboreal decomposition by cliques, we obta in one direction of the analogous result. Lemma 17. If G is a digraph, and Km tJie complete graph on m vertices, then 1 + dtw(G»Km) < m - ( l + dtw(G)). We observe that the graph in F igure 4.3 has directed tree-width 3, D-width 4, and haven-width 4, giv ing us an arbitrary 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 5m — 1 and haven-width Am> and 2. A graph with D-width 5m — 1 and directed tree-width < 4m — 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, and bramble number 3 . In this section we obtain a non- 3 The bramble number result appears in [48]. 78. t r i v ia l upper bound for D-width which is computable in polynomia l t ime when D- wid th is constant. Unfortunately there doesn't exist any algor i thm for comput ing opt imal or nearly opt imal D-decompositions. However, using the results of this section along w i th those of the previous section, we can compute non-trivial upper and lower bounds for D-width. We prove that D-width is at most the number of cops required for a restricted cop-monotone winning 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. Let a — (YQ,TT) be a winning strongly cop-monotone strategy for k + 1 cops. F rom Theorem 15, a must also be robber-monotone. Let Ua be the strategy forest associated w i th a. We define a D-decomposition (T, W) as follows: 1. V(T) = V(Ua)u{r}; 2. E(T) = E{lAa) U {(r,t)\t is a root of n a } ; 4 3. Wr = Y0; and Wt = ir(X, R) for t = (X, R) 6 V(Ua). It is clear that (T, W) has w id th at most (k + 1) — 1 = k. Because a is a winning strategy, every vertex must be occupied by a cop at some point, so for every strongly connected set S, T\s = {t\Wt n S ^ 0} ^ 0. For condit ion (D2), let S be a strongly connected set. F rom the construction of Iia and the strong cop-monotonicity of cr, for any situat ion {Yn,Rn) such that S n ixiY^^Rn) ^ 0, there is a unique path 4 For the decomposition to be undirected we ignore the directions on the edges in LTo- 79 (Yo,Ro),(Y1,R1),...,(Yn,Rn) such that S n ir(Yi,Ri) ^ 0, for 0 < i < n and S C RQ. Moreover, (YO,RQ) is common in all such paths regardless of (Yn,Rn). Hence, it suffices to show that 5 remains connected along paths of n^. Bu t this follows immediately f rom the cop-monotonicity of a: if the cops occupy some of S, leave all vertices in S, and then occupy some of S, either they revisit a vertex (contradicting cop-monotonicity), or the robber can defeat a on S (contradicting the fact that a is winning). • 4.5.1 Computing 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(nk+3), where n — |V(G)| . Furthermore, the algorithm will find such a strategy if one exists. Proof. The a lgor i thm we present in F igure 4.4 recursively computes a k-cop strongly cop-monotone strategy TT from posit ion (X, R) by iterating through al l possible val - ues for X' which preserve monotonicity, and then checking that there is a winning strategy from (X1, R') for all R' w i th a non-empty intersection w i th R. The correct- ness and running time of this algorithm follow in 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. To show that the algorithm computes a strongly cop-monotone winning strat- egy, we first show that the computed strategy is strongly cop-monotone and then prove that it is a winning strategy. For every (X, R), ir(X,R) C X U R, so TT is 80 Algorithm strategy(X, R, G, k) foreach X' C X U R with X' ± X, \X'\ = k do Let R\, i? 2 , • • •, Rrn be al l strongly connected components of G\(X' n X) that have nonempty intersection w i th R V i , let <7j = strategy(X f, R4, G, k) if <7j ^ 0,Vi, then return a = (X , 7r) where IT(X,R) = X' and cr follows Ui if the robber moves to R4. end return 0 Figure 4.4: F ind ing a strongly cop-monotone winning strategy strongly cop-monotone. To show that the strategy is winning, we show that it is winning from each posit ion (X,R). Th is is easily established by induct ion on the size of R, as TT(X, R) is defined as a set X' such that the strategy is winning from (X',R') for al l reachable positions (X',R'). A s we observed above, R' C R, and as X y£ X' C XuR, X' w i l l include vertices from R, so R! w i l l be str ict ly smaller than R. For the converse, we need to show' that if there is a &>cop strongly cop- monotone strategy a' = {YQ,IT') then ir'(X, R) is a possible return value for ir(X, R). Wi thou t loss of generality, we can assume TT'(X, R) C X U R and \TT'(X, R)\ = k as we can always transform a' into a strongly cop-monotone strategy which does satisfy these. F rom Theorem 15, a' is also a robber-monotone strategy, so R is a strongly connected component of G \ (X n rc'(X, R)). F inal ly , it is clear that if R' is a non- empty strongly connected component of G\7r ' (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(nk+2), where n = \V(G)\ . Proof. We implement the algori thm using dynamic programming. There is an entry (X, R) in the dynamic programming table n for each subset of k vertices X and each 81 strongly connected component R of G\X. The table is fil led in increasing order of the size of R. As there are at most n strongly connected components in G\X, there exist at most 0(nk+1) possibi l i ty for any (X, R) pair. In comput ing rt(X, R) we try al l possible 0(nk) subsets X' of X U R and, for each one, it takes 0 ( n 2 ) t ime to check if C is a strongly connected component of G\(X n X') (using depth-first search). Since each R4 is smaller than R, we can use dynamic programming (or memoization) so that the check of 7r(X',Ri) takes constant time' (after its in i t ia l calculation). In tota l , the running t ime of the algor i thm is 0(nk+2). • 4.6 Conclusion and Future Work In this chapter we further study D-width and identify the class of digraphs w i th D-width one. We also obta in non-trivial upper bounds for D-width in terms of the number of cops that are required to capture the robber in (strongly) cop-monotone cops/robber games. As D-width is an upper bound for directed tree-width, not only does D-width inherit a l l the algorithmic advantages of directed tree-width, such as an efficient a lgor i thm for Hami l ton ian cycle on bounded D-width graphs, but the simpl ic i ty of D-decompositions may also be used to establish other algorithmic results for digraphs w i th bounded D-width. F ind ing an algorithm for comput ing opt imal or nearly opt imal D-decompositions would have a direct effect on the efficiency of these solutions. Exp lo r ing the class of problems that are efficiently solvable on bounded D-width graphs is also a very interesting direction of future research. 82 Chapter 5 Hyper-D-width 5.1 Introduction In this, chapter, we introduce hyper-D-width and hyper-T-width as the first stable (see definit ion 9) measures of connectivity for hypergraphs. After studying some of their properties and, in part icular, proposing an algori thm for computing-nearly opt imal hyper-T-decomposition when hyper-T-width is constant, we introduce some applications of hyper-D-width and hyper-T-width in solving hard problems such as the m in imum vertex cover. 5.2 Background In this section, we review the definitions that we use in this chapter. A hypergraph H = (V, E) consists of a set of vertices V and a set of edges E where every edge e € E is a subset of V. A path in i f is a sequence of vertices u\, U2, • • • , um such that Ui and Ui+i are both in some edge in H for i = 1, 2, • • • , m — 1. We say u is connected to v if there is some path from u to v. A set S of vertices is connected if 83 every two vertices in it are connected. A connected component of H is any maximal connected set of H. For a subset X of V, the hypergraph induced by X, denoted by H[X], is (X,E')t where E' is the set of edges in E all of whose vertices are in X. F inal ly , the hypergraph H\X is H[V\X]. Notice our different interpretation of connectivity in this Chapter . Given an edge e = {u\,v2, • • • ,i>fc}, we consider it as a single connected unit meaning that e collapses by removing any of vis. Th i s is in contrast w i th those definitions that define connectivity based on the pr imal graph. Three graphs are often associated w i th any hypergraph H: The primal graph, the dual graph, and the incidence graph. The pr ima l graph is obtained by making a clique out of the vertices in every edge in H. The dual graph is obtained by rep- resenting every edge by a vertex and connecting two vertices if their corresponding edges intersect. The incidence graph is a bipart i te graph whose first part corre- sponds to vertices in H and whose second part corresponds to edges in i f . A vertex u in the first part is connected to a vertex e in the second part iiu € e in H. The tree-widths of the pr imal , dual , and incidence graphs are often referred to as primal, dual, and the incidence tree-width, respectively. A famous example of using hypergraphs is using them to model inputs to the S A T problem. A boolean formula in conjunctive normal form w i th clause sets C\,C%, • • • ,Crn of variables X = {xi,x2, • • • ,xn] and their negations x~i,x~2, • • • ,x^ is modeled by a hypergraph H = (X, E) where E = {e\, e2, • • • , em} and, for all k, x\. 6 ej iff either xk 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 hypergraph 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 problem is fixed parameter tractable. 84 Theorem 19. [51] Satisfiability of clause-sets with bounded incidence tree-width is fixed-parameter tractable. . A problem is fixed parameter tractable, if i t admits an a lgor i thm w i th running t ime 0(f(k)na) where k is some parameter independent of n, f is any function of k, and a is a constant independent of k and n. As k doesn't appear in the exponent of n, instances of large size n can be solved efficiently. Such a fact was already known for pr imal tree-width [27], but the above is stronger as the incidence tree-width is always smaller than the pr ima l tree-width plus one [51]. One parameter that is used many times in the l iterature is hypertree-width and similar variants which was first introduced by Got t lob et al. [26]. One pa- rameter that is used many times in the literature is hypertree-width and similar variants which was first introduced by Gott lob et al. [26]. A generalized hypertree decomposition of a hypergraph H = (V, E) is a triple (T, W, A), where (T,W) is a tree-decomposition of the pr imal graph of H and A is a funct ion that assigns to every vertex t of T a set of edges in E such that Wt C (J A( i ) . The w id th of (T, W, A) is the max imum of |A(t)| over all nodes t of T. (Generalized) Hypertree-width is different f rom tree-width of the pr ima l graph only in the way we measure the w id th of a tree-decomposition: Instead of counting the number of vertices in a node, we count the number of edges that cover these nodes. The generalized hypertree-width of H is the m in imum wid th over all its generalized hypertree-decompositions. A hypertree-decomposition (T, W, A) is a generalized hypertree decomposit ion that sat- isfies one special condit ion: (|J X(t))f)X(Ti) C Wt, where Tt is the subtree rooted at t and X(Tt) is ( J s e T t Ws- Th i s condit ion is added for technical reasons to make the hypertree decomposit ion computable when it is constant. It is not known whether 85 generalized hypertree-width is computable in polynomia l t ime when it is constant. The hypertree-width of H is defined accordingly. Got t lob et al. (See [26] or [25] for a survey) show how an opt imal hypertree- decomposit ion can be computed for a hypergraph w i th bounded hypertree-width by associating it w i th certain cops and robber games. They also show that the con- straint satisfaction problem is solvable in polynomia l t ime for constant hypertree- wid th 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 and Ri is a list of j tuples of values from some domain D. A solution to C S P is a valuation such that al l constraints are satisfied. A valuation V : X —• D satisfies constraint ((x\,X2,--- ,Xk),R)if (v(xi), v(x2), • • • , v(xk)) G R- In this specific model , all pos- sible valuations of the tuple Si are expl ic i t ly given, i.e. are part of the input, and, hence, the number of possible valuations is upper bounded by the input size. For example, in the S A T input 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)}) in this model. Th i s is in contrast to a typica l input to S A T (and other problems), which represents the set of values, that satisfy a constraint v i a a formula (e.g. (a V c)). In this model , if we add a big constraint (i.e. Si is big) we can make the problem easier to solve. For example, if a constraint contains all the variables, then we can simply t ry al l valuations given for that constraint and check if one works for the other constraints as well. That ' s basically why hypertree-width is related to the time required to solve CSP . Adler et a l . [2] prove that hypertree-width is wi th in a factor 3 +-e of sev- eral other hypergraph measures: generalized hypertree-width, (monotone) marshal- w id th , hyperbramble number, hypertangle number, hyperbranch-width, and hyper- linkedness. 86 5 . 3 Hyper-D-width 5.3.1 Definition Let H = (V, E) be a hypergraph. A hyper-D-decomposition of H is a pair (T, W) where T is a tree and W — {Wt\t'€. V(T)} is a f a m i l y o f subsets of V(H) such that for every connected set S: . (HI ) T\s := {t\Wt n S ^ 0} / 0, and (H2) The subgraph of T w i th vertex set T\s and edges {(s,t)\Ws D Wt n 5 ^ 0} forms a connected subtree of T . The w id th of a hyper-D-decomposition (T, W) is the max imum of \Wt\ — 1 over al l nodes t € V ( T ) . The hyper-D-width of a hypergraph is the m in imum wid th over all its hyper-D-decompositions. For example, a hyper-D-decomposition w i th w id th two for the hypergraph H = ( {1,2,3,4}, {{1,2,3}, {1,4}, {2,4}, {3,4}}) is depicted in F ig . 5.1. It's not hard to prove that i t 's, in fact, a m in imum wid th hyper-D-decomposition. F igure 5.1: A hyper-D-decomposition w i th w id th two. 87 5.3.2 Basic Properties Hyper-D-width is a generalization of tree-width. O n regular graphs, where every edge has two vertices, hyper-D-decomposition wants the two vertices in every edge to share a node. Th is is exactly what any tree-decomposition wants. Theorem 20. For every undirected graph G, tree-width{G) = hyper-D-width(G). Let (T, W) be a hyper-D-decomposition for a hypergraph H. If we make a regular graph on the vertices of H by connecting two vertices iff they share a node in T , then the result 'would be a chordal graph wi th the same tree-width as the w id th o f T . Theorem 21. For every hypergraph H with hyper-D-width w, there exists an undi- rected chordal graph G with tree-width w such that for any edge e of H with vertex set S, G[S] is connected. Hyper-D-width is inspired by D-width on directed graphs. In fact, every min ima l strongly connected set in digraphs is treated as an hyperedge in the defini- t ion of D-width meaning that hyper-D-width is,, in some sense, a generalization of D-width. 5.3.3 Stability Almost al l exist ing connectivity measures for hypergraphs are very sensitive to big edges, i.e. edges that contains many vertices. (Generalized) Hypertree-width, hy- perlinkedness, hyperbramble number, (monotone) marshal-width are all constant when we have an edge that contains all the vertices no matter what the rest of the hypergraph structure is. O n the other hand, the tree-width of the pr ima l graph.is always n — 1 for the above example, where n is the number of vertices. 88 We would like a connectivity (cyclicity) measure on hypergraphs to behave in a stable way (as tree-width does for regular graphs): adding a constant number of vertices or edges shouldn't substantial ly change the connectivity. A l l the afore- mentioned measures violate this stability condition] so do the tree-width of the dual graph and the tree-width of the incidence graph. Unl ike al l the above-mentioned connectivity measures for hypergraphs, hyper- D-width is stable. Let 's formally define stabi l i ty first and then prove the stabi l i ty 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 con- stant. Theorem 22. Hyper-D-width is stable. Proof. It's sufficient to show that hyper-D-width changes by a constant when adding one new vertex or one new edge. Assume we add a new vertex u and an arbitrary number of edges containing u to a hypergraph H. Let (T, W) be an opt imal hyper- D-decomposition of H w i th w id th w. Obviously, (T, W), where W[ = Wt U {u} for every t £ V(T), is a proper hyper-D-decomposition of the new hypergraph wi th w id th w + 1. In case we add a new edge e = {i>i,i>2, • • • , Vfc} to the hypergraph H, (T,W), where W[ = Wt U {vx} for every t 6 V(T), is a proper hyper-D- decomposit ion of the new hypergraph w i th w id th at most w + 1. • In contrast, all the existing alternative measures are unstable. Theorem 23. (Generalized) Hypertree-width, hyperlinkedness, hyperbramble num- ber, (monotone) marshal-width, (dual, incidence, or primal) tree width are all un- 89 stable. Proof. It's proven in [2] that the first four parameters are w i th in a constant factor of each other. Hence it suffices to prove hypertree-width and (dual, incidence, primal) tree w id th are unstable. Let if" be a hypergraph wi th big hypertree-width. A d d i n g one edge that contains al l the vertices makes the hypertree-width equal to one. Thus , hypertree-width is unstable. Similarly, the pr imal tree w id th is unstable. Now, let i f be a hypergraph w i th small dual tree-width. Let i f ' be obtained from i f by adding a new vertex u and all possible edges that contain u (i.e. 2 n edges where n is the number of vertices). The dual graph of i f ' has a clique of size 2 n (all edges that contain u) which means it has dual tree-width at least 2 n — 1, which shows dual tree-width is unstable (under removal of vertex u).. A s for the incidence graph suppose i f is a hypergraph wi th small incidence tree-width. We show that i f ' , as constructed above, has large incidence tree-width. Let I be the first ^ vertices of i f . The number of edges in i f ' that contain al l vertices in I is at least 2 2 which means the incidence graph of i f ' contains a Kn " ( ac tua l l y K„ a as well) subgraph. 2' 2 2' Hence, its tree-width is at least | . • 5.3.4 Comparison In this section we compare hyper-D-width w i th other existing parameters defined on hypergraphs, namely, hypertree-width and the tree-width of the pr imal , dual , and 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. The first inequality follows from the fact that every tree-decomposition of the pr ima l graph is a hyper-D-decomposition. O n the other hand, there exist hy- pergraphs w i th pr ima l tree-width n — 1 and hyper-D-width one (a hypergraph w i th one edge containing all the vertices). As for the incidence tree w idth , let (T, W) be a tree-decomposition of the incidence graph. For each edge e = {v\, v2, • • • , Vk}, replace every occurance of e in Wt for t G V(T) w i th v\. Since e and v\ share some node of T, i.e. {e, vx} C'Wt for some t G V(T), the nodes that contain v\ st i l l make a connected subtree. Moreover, since e shares some node w i th every v-i, 1 < i < k, the vertices v\)v2) - • • ,Vk make a connected subtree in the resulting tree-decomposition. Aga in , there are hypergraphs w i th smal l hyper-D-width, but large incidence tree-width. Assume H has 2n vertices {1, 2, • • • , 2n} and n edges of the form e$ = {1, 2, • • • , n, n + i] for 1 < i < n. The incidence graph has a Kn>n subgraph (every i is connected to ej for 1 < i, j < n) and, hence, has tree-width at least n. However, its hyper-D-width is one. Its m in imum w id th hyper-D-decomposition is a star w i th root r containing Wr = {1} and ith leaf containing Wi — {l,i} for 2 < i < In. Almost the same statement holds when comparing the dual tree w id th and hyper-D-width. G iven a tree-decomposition (T, W) w i th w id th w of the dual graph of hypergraph H, we show how a hyper-D-decomposition of H w i th w id th at most w + 1 can be constructed l . For any vertex u G V(H), al l edges that contain u make a clique in the dual graph. Hence, there is some node in T , say X(u), that contains all such edges. In the first step, for all u G V(H) we add a leaf l(u) w i th Wj(u) = WA(U) O {u} a n d attach it to the node X(u) in T . Next , 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 arbitrary vertex v 6 e and replace e w i th v in every Wt for £ € V(T). C a l l the resulting decomposit ion (T',W). Now, (T", W ) contains only vertices of H. We cla im that (T',W) is a hyper-D-decomposition of H. F i rs t , the new leaves insure that every vertex u G H is contained in some Wt (in part icular, Wj( u)) in T". Second, for any vertex u € H, all nodes £ 6 X" such that it € W t ' make a connected subtree. Every edge e replaced by u in creating T ' , forms a connected subtree in T that contains the node X(u). Hence, these subtrees are connected in T" and they connect to 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'\Xj ^ 0. In fact, X(XJ) G T'\Xl n T " ^ . . So the subtrees corresponding to vertices of e form a connected subtree. A star graph of size n has tree-width one and (by Theorem 20) hyper-D-width one whereas its dual graph is a clique and, 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 in terms of the number of cops that are required to win certain cops/robber game. A n identical definit ion of cops and robber games under the new definit ion of connected components enable us to obta in 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 0(nk+2). 5.3.6 Applications In this section we show that there exist polynomial-time approximat ion schemes ( PTAS ) for many problems including vertex cover, dominat ing set, and mult icut problems on hypergraphs when the hyper-D-width of the input hypergraph is con- stant. Let a generic problem P be as follows: F i n d a min imum number o f vertices in a hypergraph that satisfy some constraint C. We are especially interested in problems P w i th the following property. (Decomposable Property)Problem P is decomposable if it satisfies the following condit ion. Let i f be a hypergraph. For any subset X of vertices of H, let C i , C2, • • • , Cm be the connected components of H\X. Let Di be a solution for P on H[d]. Then , X U ( D i U D2 U • • • U Dm) is a solution of P on H. The decomposable property lets us choose any suitable X, put it in the solution, break the input hypergraph into smaller parts, and solve the problem on each part independently. It's easy to verify that multi-cut, dominat ing set, and vertex cover are examples of such problems. For example, for the vertex cover ' problem, if we choose all vertices in X then any edge that intersects both Ci and Cj (i 7̂ j) is covered. The rest is, then, solving the vertex cover problem on each Ci separately. Now, we show how such problems have a P T A S on bounded hyper-T-width 9 3 hypergraphs. The idea is similar to the technique that Cal inescu et al . [15] use to f ind a P T A S for mult icut on bounded tree-width graphs and digraphs. Let (T, B, W) be a hyper-T-decomposition w i th w id th w for the input hypergraph. Let t € V(T) be the bottom-most node such that there exists an opt imal global solution that contains at least w/e vertices in the subtree Tt rooted at t. If there is no such t then the opt imal global solution has fewer than w/e vertices. Such a solution can be computed in t ime 0(nw/e). Otherwise, let optt be the number of vertices of an opt imal solution in T t . Choosing and removing all vertices in A t = Bt U [Je^tWe breaks Tt into several connected components each having less than w/e vertices of the opt imal solution. Hence, the problem can be solved by brute force on al l these components in t ime 0(nw^e). Hence, the number of vertices that we pick is at most optt + w < optt(l + e). Assume that the rest of the hypergraph has o vertices in the opt imal solution. Accord ing to the induct ion hypothesis, we can find a solution w i th at most o ( l + e) vertices. Hence, we can solve the problem on H by choosing at most (1 + e)(optt + o) vertices, y ielding a (1 + e)-factor approximat ion for P. The details of the algor i thm are shown in F ig . 5.2. To complete this section we prove that all aforementioned problems are hard even on bounded hyper-D-width hypergraphs. Theorem 26. The vertex cover problem, the dominating set problem, and the mul- ticut problem are NP-Complete on bounded hyper-D-width hypergraphs. Proof. Let C\, C2, • • • , Cm be a S A T problem instance over variables x\, x2, • • * , xn. We make a hypergraph H = (V, E) w i th vertex set V = Ui<i<n{xi,x~i, Zi} \J{u} and edge set e$ = C j U {u}, for 1 < i < m and e m + j = { X J , S 7 , Zi}, for 1 < i < n. We c la im that the S A T problem instance is satisfiable iff the hypergraph H has a vertex cover of size exactly n. Assume the S A T instance is satisfiable w i th setting all Xj 's 94 Input: A hypergraph H together w i th an opt imal hyper-D-decomposition (T, W) Output: M i n i m u m number of vertices that satisfy P •/* Let Let Xt = \Jt>eTtWt,. */ foreach t e T d o Let ti, i = 1, 2, • • • , m, be children of t. foreach i do find an opt imal solution o.L to P of size at most w/e for H[XU - Wt]. If no such solution exist then try the next t. end Let o = UjOj . Recursively find a (1 + e)-factor approximat ion solution d for H\Xt- Let optt = oUdUWt. end return optt w i th m in imum size. F igure 5.2: Solving decomposable problem P on a bounded hyper-D- width hypergraph in a set X to be true and the rest to be false. In the hypergraph let the vertex cover be X U {x~i\xi 0 X}. Obviously, every edge of type Q U {u} and every edge of type {xi,x~i,Zi} is covered and the size of the vertex cover is n. O n the other hand, let X be a vertex cover of size at most n. Obviously, it must have picked exactly one vertex from every tr iple {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~[. in d, which makes a satisfiable solution. F inal ly , we mention that the hypergraph constructed above has hyper-D-width at most three. Make a star w i th root u and every leaf containing {u, Xi,xi, Zi}, for 1 < i < n. It's easy to prove that the above reduction works for the dominat ing set problem as well. The NP-Completeness of the mult icut problem follows from its NP-Completeness on bounded tree-width graphs proven by Cal inescu et al. [15]. • 95 5 . 4 Introducing hyper-T-width Al though hyper-D-width has many nice properties and resembles undirected tree- w id th in a natural way, it has one big disadvantage that we haven't resolved yet: We don't know a polynomia l t ime algori thm for comput ing opt imal or even approx- imately (within a constant factor) opt imal hyper-D-decompositions for bounded hyper-D-width hypergraphs. One opt ion is to consider a generalization of directed tree-width [34, 35] instead. Recal l the following definit ion 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 decomposit ion 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 = {W e|e G E(T)} are sets of subsets ofV(G) that satisfy: (RI) B is a partition of V(G) into (possibly empty) sets such that Br ^ 0 for the root r of T, and (R2) If e G E(T), then B\ := \J{Bt\t > e] is We-normal or empty. The w id th of an arboreal pre-decomposition (T,B,W) is the minimum k such that for all t G V(T), \Bt U U e~t^e| < k + 1. An arboreal decomposit ion is a pre- decomposition in which all Bt are non-empty, and the directed tree-width of a di- graph G, dtw(G), is the minimal width of all its arboreal decompositions. 96 D-decomposition is, in fact, a restricted variant of arboreal pre- decomposi- t ion. G iven a D-decomposition (T, W) of w id th IU of a digraph G, the following is an arboreal pre-decomposition of w idth w for G. (T', B', W), where T' is obtained from T by choosing a random root and directing all edges away from the root. For any edge e = (u, v) -in T", B'v = Wv - Wu and Xe = Wvn Wu. Accord ing to Johnson et al . [34] a set S is Z-normal if every path from a vertex in S to another vertex in S that contains a vertex in V(G) — S has a vertex in Z as well. O n the other hand, there is no strongly connected component of G\Z that contains vertices from both S and V(D) — S. Inspired by the above definit ion, we define hyper-T-width as follows. D e f i n i t i o n 12 ( 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- decomposit ion 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 — {We\e G E(T)} are sets of subsets ofV(H) that satisfy: (RI) B is a partition of V(H) into possibly empty sets such that Br / 0 for the root r of T, and (R2) If e G E(T), then B^ := \J{Bt\t > e} is We-normal or empty. A set S is Z-normal if there is no connected component of H\Z that contains vertices from both S andV(H) - S. The w id th of a hyper T-decomposition (T.B,W)' is the minimum k such that for all t G V(T), \Bt U Ue^t We\ < k + 1. The hypef T-width of a hypergraph H is the minimal width of all its hyper T-decompositions. In the following section we show that hyper-T-width has al l the nice prop- erties of hyper-D-width. It's stable, has the balanced-separator property, and has 97 al l currently known algorithmic advantages of hyper-D-width. In addit ion, we can compute an approximate hyper-T-decomposition when 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 when adding one new vertex or one new edge. Assume we add a new vertex u and an arbitrary number of edges containing u to a hypergraph H. Let (T,B,W) be an opt imal hyper-T-decomposition of H of w id th w. Obviously, (T, B', W ) , where W[ = Wt U {u} for every t G V(T) and B'r = Br, when r is not the root and B'r — Br U {u} for the root r, is a proper hyper-T-decomposition of the new hypergraph. Moreover, (T, B', W') had w id th 'tu + 1. In case we add a new edge e = {vi,V2, • • • , ffc} to the hypergraph H, (T, W ' , 73'), where W[ = Wtli {vi} for every t G V ( T ) , is a proper hyper-T-decomposition of the new hypergraph. • As mentioned in 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. Th i s is a direct consequence of Theorems 24 and 28. • 98 As for algorithmic applications of hyper-T-width we show that a problem P that satisfies the decomposable property admits a P T A S on bounded hyper-T-width hypergraphs. The idea is quite similar to hyper-D-width. We consider the deepest edge e = (r, r') (i.e. r has max imum depth) such that the subgraph Be has more than j vertices of some opt imal solution, where w is the hyper-T-width of the input hypergraph and e is any constant. Now adding all vertices Xe in the solution does not change the number of vertices in the solution by more than a mult ipl icat ive factor 1 + e. 5.4.2 Computation The big advantage of hyper-T-width over hyper-D-width is the fact that we can' approximately compute it when it is constant. Johnson et al. [34] prove this for directed tree-width and their proof generalizes immediately to hypergraphs. In part icular, they introduce the notion of haven order and prove that directed tree- w id th and haven order are w i th in 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. Their proof for tree-width(G) < 3LT(G) + 1 is constructive. If the haven order of G is at most w then it builds an arboreal decomposit ion of w id th at most 3w+l. In this section we show that the construction quickly transfers to hypergraphs without any major change. We basically mimic the proof of Johnson et al . [34] here. As our definitions of connectivity and havens are different from theirs, the proof is completely i l lustrated below. Let 's start w i th 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 component of H \ Z such that ifXCYC V(H). and \Y\ < k then 3(Y) C B(X). 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) Let (T, W, B) be a hyper-T-decomposition of w id th w of H. For any node t let Xt — BtU U e ~t We- F h s t observe that w + 1 cops can catch a robber in the cops/robber game. Assume a hyper-T-decomposition (T, W, B) of G of w id th w is given. The cops can start at XQ = A r , where r is the root. Let T\,T2, • • • ,Tm be subtrees of T w i th roots ri,r2, - • • ,rm, chi ldren of r. Let = (r, ri). Accord ing to conditions of hyper-T-decompositions, the robber can only be at vertices in one of the sets B^. The cops can then move to XTi and continue the strategy unt i l they trap the robber in one of the leaves. O n the other hand if H has a haven of order h then the robber has a winning 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(i J ) . (Right inequality) Assume H has no haven of order w. F i rs 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. Assume not. Then for every set Z w i th \Z\ < w there is one connected 100 component of Z , say 0(Z), such that \B(Z) f l Y\ > w. But , this is a contradict ion as B is a haven of order w. For any Z and Z ' w i th Z C Z ' and |Z'| < w, bo th /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 which means B(Z') C /3(Z)'. . • s Consider a hyper-T-decomposition (T, PF, J5) of H w i th the following restric- tions. 1. For any node r, if r is not a leaf then |£?r| < w and |A r | < 3w — 1. 2. For any edge e, |W e| < 2w — 1. 3. Subject to the above conditions we take the hyper-T-decomposition that m i n - imizes the max imum of |J5r|, for all r's. A s the obvious hyper-T-decomposition w i th one vertex r and BR = V(H) sat- isfies the 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 th \BR\ > r then we are done and (T, W, B) would have w id th at most 3w — 2. Otherwise, take the leaf r w i th max imum ]BR\. Assume r' is the unique root of r, e = (r',r) and Y = WE. Accord ing to lemma 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 from Y. Let Z = Z U {u} for some arbitrary vertex u in BR. We bui ld a new hyper-T-decomposition satisfying the first two conditions, but a smaller \BR\ which is a contradict ion. Let X\,X2, ••• ,XM be the connected components of H[BR]\Z. We create m new leaves r i , ^ , - - - ,rm and connect them to r (i.e. create edges from r to' each ri). Set BN = .Xi and change BR to .Z D BR. For the edge = (r, r,) set 101 Wei = Z U ( y n Xi). A s \Y nXi\ < 2w - 1 this insures that \Wei| satisfies condit ion 2. B y the way, A r = Z U Y; thus, |A r | <3w - 1 . • The .p roo f that hyper-T-width( i f ) < 3H(H) + 1 is constructive and can be used to obta in an approximate hyper-T-decomposition. There is at most n opt imizat ion steps dur ing which we find a set Z and add now leaves to the existing hyper-T-decomposition. F ind ing a set Z of size less than w and verifying that al l connected components H\Z contain less than w vertices of Y can be done in t ime 0(nw+2). Hence the. total running time for f inding an approximate hyper-T- decomposit ion would be 0(n™+3). 102 Chapter 6 Conclusions and Research Directions In this thesis we covered problems related to metric embedding and tree-width. We obtained a low distort ion embedding of series-parallel graphs into £\, computed opt imal embeddings between line metrics when the distort ion was small enough, and proposed tree-width-like connectivity measures, D-width, hyper-D-width, and hyper-T-width , for digraphs and hypergraphs. As series paral lel graphs and /c-outerplanar graphs have bounded tree-width and both are known to have constant distort ion (for constant k) embedding into £i, bounded tree-width graphs are conjectured to have bounded distort ion embedding into £\. Since a good distort ion embedding into £\ implies good-approximation for several fundamental problems, such as the sparsest cut and mult icut problems, the study bounded tree-width graphs and their connection to £\ metrics becomes important . Such a connection between tree-width and metric embedding and, also, the 103 fact that the study on tree-width has found numerous applications in practice, i n - spires people to extend it to similar class of objects: digraphs and hypergraphs. A m o n g many proposed measures for directed graphs, D-width seems to 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 than pr imal , dua l , and incidence tree-width. They also have appl icat ion in m in imum vertex cover, m in imum dominat ing set, and mult icut problems. 6.1 £\ metrics We've proven that the algorithm given by G u p t a et al. gives an embedding w i th distort ion at most 6.0 for every series parallel graph, but gives distort ion at least 3.0 even for some outerplanar series parallel graphs. A n interesting open problem is to close this gap. Some other relevant open problems are min imiz ing the number of used dimensions (which is exponential w i th 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 th bounded distort ion. 6.2 Line metrics We currently know how to compute an opt imal embedding between two line metrics when the opt imal distort ion is small (less than 13.602) and know it is hard to do so when the distort ion is at least n e for some constant e [29]. A n open problem is to close this gap and, for example, study its hardness when the distort ion is 0 ( l o g e n ) . Another very interesting problem is to look for embeddings that have close to the opt imal distort ion. A l though f inding a constant-factor approximat ion when the 104 opt imal distort ion is at least n e is hard [29], finding such an approximate distort ion seems to be a lot (easier for smaller distortions. 6.3 D-width A very challenging open topic is to study the connection between D-width and d i - rected metrics or directed cut problems. Bounded D-width digraphs admit P T A S for multi-cut • problems (when two vertices are considered separated if they belong to two different strongly connected components). Chuzhoy and K h a n n a [20] re- cently proved than the sparsest cut problem and the mult icut problem are hard to approximate w i th in a factor 2 n ( l o g l 6 n ) for any constant e even on directed acyclic graphs. Th is is a big negative result that basically says that D-width and directed tree-width are irrelevant to cut problems and directed metrics, but st i l l leaves the open problem of studying digraph classes that admit constant-factor approximate solutions for cut problems. One other research direction is to explore other algorithmic aspects of D- wid th such as its computat ion w i th D-width is constant. 6.4 Hyper-D-width Hyper-D-width and hyper-T-width are very new and there exist several open prob- lems related to them. A n efficient algorithm (showing it is fixed parameter tractable in particular) for comput ing opt imal (or approximate) hyper-D-decompositions for smal l hyper-D-width would be very useful problem. Exp lo r ing algorithmic aspects of hyper-D-width and hyper-T-width is also a very nice research direction. There are some fundamental problems (such as solving CSP , S A T , and finding Nash Equ i l i b r i a 105 of certain games) that seem to be relevant to hyper-D-width and hyper-T-width and finding those connections is an interesting problem. 106 Bibliography [1] Isolde Adler . Directed tree-width examples. Journal of Combinatorial The- ory(Series B), 2007. To appear. [2] Isolde Adler , Georg Gott lob, and M a r t i n Grohe. Hypertree-width and related hypergraph invariants. In Stefan Felsner, editor, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), volume A E of DMTCS Proceedings, pages 5-10. Discrete Mathemat ics and Theoret ical C o m - puter Science, 2005. [3] Michae l H. A lber t and Mike D . 'A tk inson . Simple permutations and pattern restricted permutations. Discrete Mathematics, 300(1-3): 1-15, 2005. [4] A . Andon i , M . Deza, A . Gupta , P. Indyk, and S. Raskhodnikova. Lower bounds for embedding edit distance into normed spaces. In Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithm, pages 523-526, Phi ladelphia , P A , U S A , 2003. Society for Industr ial and App l i ed Mathemat ics . [5] M ike A tk inson and Derek Hol ton, editors. Permutation patterns. E lectronic Journal of Combinator ics, Clemson, SC , 2003. Including selected papers from the conference held in Otago, February 10-14, 2003, E lectron. J . Comb in . 9 (2002/03), no. 2. 107 [6] Y . A u m a n n and Y . Raban i . A n o(log k) approximate min-cut max-fiow theorem and approximat ion algori thm. SIAM Journal on Computing, 27, 1998. [7] D. Av i s and M . Newborn. O n pop-stacks in.series. Utilitas Mathematica, 19:129-140, 1981. [8] M i h a i Bado iu , Ju l i a Chuzhoy, P io t r Indyk, and Anastasios Sidiropoulos. Low- distort ion embeddings of general metrics into the line. In Proceedings of Annual ACM Symposium on Theory of Computing, pages 225-233, New York , N Y , U S A , 2005. A C M Press. [9] M i h a i Bado iu , Kedar Dhamdhere, A n u p a m Gup ta , Y u r i Rabinovich, Hara ld Racke, R. Rav i , and Anastasios Sidiropoulos. Approx imat ion algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of An- nual ACM-SI AM Symposium on Discrete Algorithm, pages 119-128, Ph i lade l - phia, P A , U S A , 2005. Society for Industr ia l and App l i ed Mathemat ics . [10] Dietmar Berwanger, Anu j Dawar, Pau l Hunter, and Stephan Kreutzer . Dag- wid th and parity games. In The 23rd International Symposium on Theoretical Aspects of Computer Science, pages 524-536, 2006. [11] M ik los Bona . A survey of stack-sorting disciplines. Electr. J. Comb., on(2), 2002. [12] Prosenjit Bose, Jonathan F. Buss, and A n n a Lub iw . Pat tern matching for permutations. Inf. Process. Lett, 65(5):277-283, 1998. [13] J . Bourgain. O n l ipschitz embeddings of finite metric spaces in hi lbert spaces. Israel Journal of Mathematics, 52:46-52, 1985. 108 [14] W i l l i a m John B r inkman . Metric Space Emebeddings into l\: An optimization approach. P h D thesis, Pr inceton University, November 2004. . [15] G r u i a Cal inescu, C r i s t ina G . Fernandes, and Bruce Reed. Mu l t i cu ts in un - weighted graphs and digraphs w i th bounded degree and bounded tree-width. Journal of Algorithms, 48(2):333-359, 2003.. [16] Douglas E. Car ro l l , Ash ish Goel , and A d a m Meyerson. Embedd ing bounded bandwidth graphs into 11. I i i The 33rd International Colloquium on Automata, Languages and Programming, pages 27-37, 2006. [17] N ishanth Chandran , Ryan Moriarty , Rafa i l Ostrovsky, Omkant Pandey, and A m i t Sahai. Improved algorithms for opt imal embeddings. Electronic Collo- quium on Computational Complexity (ECCC), (TR06-110), 2006. [18] Moses Char ikar , Konstant in Makarychev, and Yu r y Makarychev. Directed met- rics and directed graph part i t ioning problems. In Proceedings of Annual ACM- SIAM Symposium on Discrete Algorithm, pages 51-60, New York , N Y , U S A , 2006. A C M Press. [19] Chandra Chekur i , A n u p a m Gupta , Ilan Newman, Y u r i Rabinovich, and Al is ta i r Sinclair. Embedd ing fc-outerplanar graphs into £\. In Proceedings of Annual . ACM-SIAM Symposium on Discrete Algorithm, pages 527-536, Phi ladelphia , P A , U S A , 2003. Society for Industr ial and App l i ed Mathemat ics . [20] Ju l i a Chuzhoy and Sanjeev Khanna . Po lynomia l flow-cut gaps and hardness of directed cut problems. In Proceedings of Annual ACM Symposium on Theory of Computing, New York, N Y , U S A , 2007. A C M Press. 109 [21] D .G . Cornei l , H. Lerchs, and L. Stewart Bur l igham. Complement-reducible graphs. Discrete Applied Math., 3:163-174, 1981. [22] R. Diestel. Graph Theory. Springer, 3rd edit ion, 2005. [23] S. Even and A . Itai. Queues, stacks, and graphs. In Theory of Machines and Computations, Z. Kohavi and A. Paz, Eds., pages 71-86, New York , N Y , U S A , 1973. Academic Press. • \ [24] M . R. Garey and Dav id S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W . H. Freeman, 1979. [25] Georg Got t lob , M a r t i n Grohe, Nysret Mus l i u , Marko Samer, and Francesco Scarcello. Hypertree decompositions: Structure, algorithms, and applications. In Dieter Kra tsch , editor, Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG05), volume 3787 of Lec- ture Notes in Computer Science, pages 1-15. Springer-Verlag Ber l in Heidelberg, 2005. [26] Georg Got t lob , N ico la Leone, and Francesco Scarcello. Hypertree decomposi- tions and tractable queries. Journal of Computer and System Sciences, 209:1- 45, 2002. [27] Georg Got t lob , Francesco Scarcello, and M a r t h a Sideri. Fixed-parameter com- plexity in ai and nonmonotonic reasoning. Artif. IntelL, 138(l-2):55-86, 2002: [28] A n u p a m Gup ta , A l i s ta i r Sinclair, I lan Newman, and Y u r i Rabinovich. Cuts , trees and £i-embeddings of graphs. Combinatorica, 24(2):233-269, A p r i l 2004. [29] A lexander Ha l l and Christos Papadimi t r iou . Approx imat ing the distort ion. In APPROX-RANDOM, pages 111-122, 2005. 110 [30] Roger A . Horn and Charles R. Johnson. Matrix analysis. Cambridge Univers i ty Press, New York , N Y , U S A , 1986. [31] Pau l Hunter and Stephan Kreutzer . D igraph measures: Ke l l y decompositions, games, and orderings. In Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithm, New York, N Y , U S A , 2007. A C M Press. [32] Pau l Hunter and Stephan Kreutzer . D igraph measures: Ke l l y decompositions, games, and orderings. Theoretical Computer Science, 2007. Submitted. [33] P. Indyk. A lgor i thmic applications of low-distortion geometric embeddings. In Proceedings of IEEE Symposium on Foundations of Computer Science, page 10, Washington, D C , U S A , 2001. I E E E Computer Society. [34] T . Johnson, N . Robertson, P. D. Seymour, and R. Thomas. Directed Tree- W i d t h . Journal of Combinatorial Theory (Series B), 82:128-154, 2001. [35] T . Johnson, N . Robertson, P. D. Seymour, and R. Thomas. A d d e n d u m to "Directed Tree-Width" . manuscript, 2002. [36] Cla i re Kenyon, Yuva l Raban i , and Al is ta i r Sinclair. Low distort ion maps be- tween point sets. In Proceedings of Annual ACM Symposium on Theory of Computing, pages 272-280, New York, N Y , U S A , 2004. A C M Press. [37] T . K loks . Treewidth, Computation and Approximation. Ber l in : Springer- Verlag, 1994. [38] Dona ld E. K n u t h . Art of Computer Programming, Volume 1: Fundamental Algorithms. Add i son Wesley Professional, 1973. I l l [39] Na than L in i a l , E r an London, and Yu r i Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245, 1995. [40] Jan Obdr lek. Dag-width: connectivity measure for directed graphs. In Proceed- ings of Annual ACM-SIAM Symposium on Discrete Algorithm, pages 814-821, New York , N Y , U S A , 2006. A C M Press. [41] H. Okamura and P. D. Seymour. Mu l t i commodi t y flows in planar graphs. Journal of Combinatorial Theory (Series B), 31:75-81, 1981. [42] Vaughan R. P ra t t . Comput ing permutations w i th double-ended queues, parallel stacks and parallel queues. In Proceedings of Annual ACM Symposium on Theory of Computing, pages 268-277, New York , N Y , U S A , 1973. A C M Press. [43] Satish Rao. Smal l distort ion and volume preserving embeddings for planar and euclidean metrics. In SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry, pages 300-306, New York, N Y , USA , . 1999. A C M Press. [44] B. Reed. Tree w id th and tangles: A new connectivity measure and some ap- plications. Suervey in Combinatorics, 241:87-158, 1997. [45] B. Reed. Introducing directed tree w idth . In H.J. Broersma, U. Faigle, C . Hoede, and J . L . Hur ink , editors, Electronic Notes in Discrete Mathemat- ics, volume 3. Elsevier, 2000. [46] B. Reed, N . Robertson, P. Seymour, and R. Thomas. O n packing directed circuits. Combinatorica, 16:535-554, 1996. [47] M .A . Safari. Directed tree-width. Master 's thesis, School of Computer Science, University of Waterloo, 2003. 11.2 [48] M o h a m m a d A l i Safari. D-width: A more natural measure for directed tree width.. In Joanna Jedrzejowicz and Andrzej Szepietowsk, editors, Proceedings 30th International Symposium on Mathematical^Foundations of Computer Sci- ence, MFCS'05, Lecture Notes in Computer Science, volume 3618, pages 745- 756, Ber l in , 2005. Springer-Verlag. [49] James H. Schmerl and W i l l i a m T . Trotter. Cr i t i ca l l y indecomposable part ia l ly ordered sets, graphs, tournaments and other binary relational structures. Dis- crete Math., 113(l-3):191-205, 1993: • [50] P. Seymour and R. Thomas. G raph searching, and a min-max theorem for treewidth. Journal of Combinatorial Theory (Series B), 58:239-257, 1993. [51] Stefan Szeider. O n fixed-parameter tractable parameterizations of sat. In SAT, pages 188-202, 2003. [52] Robert Tarjan. Sort ing using networks of queues and stacks. J . ACM, 19(2):341-346, 1972. [53] D. H. Younger. Graphs w i th interl inked directed circuits. In Proceedings of the Mid-west Symposium on Circuit Theory, volume 2, pages X V I 2.1 - X V I 2.7, 1973. 113
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- D-width, metric embedding, and their connections
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
D-width, metric embedding, and their connections Ali Safari, Mohammad 2007
pdf
Page Metadata
Item Metadata
Title | D-width, metric embedding, and their connections |
Creator |
Ali Safari, Mohammad |
Publisher | University of British Columbia |
Date | 2007 |
Date Created | 2011-02-18 |
Date Issued | 2011-02-18 |
Description | Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems. In particular, embedding to an [cursive l]₁ norm has been used as the key step in an approximation algorithm for the sparsest cut problem. The sparsest cut problem, in turn, is the main ingredient of many algorithms that have a divide and conquer nature and are used in various fields. While every metric is embeddable into [cursive l]₁ with distortion O (log n) [13], and the bound is tight [39], for special classes of metrics better bounds exist. Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into [cursive l]₁ [41]. Series-parallel graphs [28] and k-outerplanar graphs [19] (for constant k) are embeddable into[cursive l]₁ with constant distortion planar graphs and bounded tree-width graphs are conjectured to have constant distortion in embedding to [cursive l]₁ . Bounded tree-width graphs are one of most general graph classes on which several hard problems are tractable. We study the embedding of series-parallel graphs (or, more generally, graphs with tree-width two) into [cursive l]₁ 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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | Eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2011-02-18 |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0052053 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
URI | http://hdl.handle.net/2429/31491 |
Aggregated Source Repository | DSpace |
Download
- Media
- 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
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 28 | 1 |
Germany | 18 | 1 |
United States | 4 | 0 |
Japan | 3 | 0 |
City | Views | Downloads |
---|---|---|
Beijing | 23 | 0 |
Unknown | 18 | 1 |
Shenzhen | 5 | 1 |
Ashburn | 3 | 0 |
Tokyo | 3 | 0 |
Sunnyvale | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
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>
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