Graph Decomposition and a Greedy Algorithm for Edge-disjoint Paths Kasturi Varadara jan 1 Intro duction Ganesh Venkataraman They also present a class of instances for which the approximation guarantee of the greedy algorithm is (n2/3 ) and hence the bound we show is nearly tight. Independent of our work, Ha jiaghayi and Leighton (personal communication) prove a weaker version of Theorem 1.1 with a bound of O(n3 /l3 ) on the size of C ; using this, they show that the greedy algorithm is an O(n3/4 ) approximation for the EDP problem. 2 Key Lemma We introduce certain conventions and notations that will be used throughout this paper. For any graph G = (V , E ) and any subset C E of edges, let G\C denote the graph G = (V , E - C ). (u v )G denotes that there is a path from the vertex u to the vertex v in the graph G; ¬(u v )G denotes that there is no such path. Let (G, C ) = {(u,v) | (u v )G and ¬(u v )G\C }. dG (u, v ) represents the shortest path distance between u and v in G; we will drop the subscript when the graph G being referred to is clear. All graphs that we deal with are directed with unit edge costs unless otherwise specified. The main result of this paper is the following theorem: Theorem 1.1. Let G = (V , E ) be a directed graph with n vertices and l 1 a parameter. There exists a set C E of O((n2 /l2 ) log2 n/l) edges such that for every pair u, v V such that (u v )G and dG (u, v ) l, there is no path from u to v in G\C . Lemma 2.1. Let G = (V , E ) be a directed graph with n vertices and l log n. Suppose there are two vertices s, t in G such that (s t)G and d(s, t) l. Then there exists a subset C E and a constant c > 0 such that |C | c n 2 log2 ( ) |(G, C )| l l To prove the lemma we proceed to construct a series of graphs starting from G. Let Li = {v | d(s, v ) = i} The above theorem implies that the greedy algorithm denote the set of vertices at the i'th level in a BFS for computing edge disjoint paths (EDPs) in directed starting from s. Note that L0 = {s} and L0 , . . . , Ll are graphs is an O(n2/3 log2/3 n) approximation algorithm. non-empty. We use a parameter which will be defined This bound is also the best known approximation factor later. As of now, we can treat as a small number for the EDP problem in terms of the number of vertices. such that 1/ is an integer. For 0 j 2/ , let Gj The approximability of this problem in terms of the be the subgraph of G induced by the vertices in levels number of edges is better understood [2, 3, 4, 5]; see the Lj l/8 , . . . , Ll-j l/8 . We call Lj l/8 the "first level" in discussion in [1]. In the edge disjoint paths problem, Gj and Ll-j l/8 the "last level" in Gj . Now, define we are given a directed graph and a set of pairs of a series of threshold values corresponding to every Gj . j. Let Cj vertices and the goal is to connect as many pairs as The threshold value tj for Gj equals (n/l) denote a minimum cut in Gj that separates every vertex possible by paths with the constraint that no two paths share an edge. Chekuri and Khanna [1] analyze the in the first level of Gj from every vertex in its last level. greedy algorithm for this problem: among all unrouted By our definitions of Gj , the last graph G2/ has at least l pairs, pick the closest in the graph consisting of yet i /2 levels of G in it. This implies that the min-cut C2/ 22 unused edges, and connect then using the shortest n G2/ has size O(n /l ) which is O(t2/ ). The minpath in this graph. Plugging Theorem 1.1 into their cut C0 in G0 has size at least t0 = 1. Therefore, there analysis, we obtain that the greedy algorithm is an exists a y with 1 y 2/ such that |Cy-1 | ty-1 u O(n2/3 log2/3 n)-approximation. Chekuri and Khanna and |Cy | = O(ty ). Choose such a y and consider the c2 t Cy . We will show below that (G, Cy ) = (|Cy-1 | 2l ). proved a weaker version of Theorem 1.1 with a bound of O(n4 /l4 ) on the size of C , which implied that This implies that the greedy algorithm is an O(n4/5 ) approximation. |Cy | |Cy | ty = O( ) = O( ) Supp orted by an NSF CAREER award CCR-0237431 |(G, Cy )| |Cy-1 | 2l2 ty-1 2l2 University of Iowa, kvaradar@cs.uiowa.edu 1 1n University of Iowa, gvenkata@cs.uiowa.edu = 2 O( ( ) ). l 2l Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 379 Setting = 1/ log(n/l) , we get: 1 n |Cy | = O( 2 log2 ( )). |(G, Cy )| l l What remains to be shown is that (G, Cy ) (|Cy-1 | 2l2 ). We first prove the following claim. = get the bound defined in the above theorem. So we only consider the case when l log n. The following algorithm gives a cut that satisfies the property stated in the theorem. Algorithm Min-cut 1. G1 = G, i 1 2. While s and t such that (s t)Gi and dGi (s, t) l (a) find a set Ci of edges in Gi such that O( l1 log2 n ) 2 l (b) Gi+1 Gi \Ci (c) i i + 1 end while 3. Return C = Ci |Ci | |(Gi ,Ci )| Claim 2.1. Suppose Li-1 , Li , Lk , Lk+1 Gy-1 where i < k . Then the number of pairs (u, v ) such that u Li-1 Li and v Lk Lk+1 and (u v )Gy-1 is at least |Cy-1 |. Proof. It is easy to see from the max-flow min-cut theorem, the integrality of the optimal flow, and flow decomposition of the optimal flow that there are |Cy-1 | edge-disjoint paths in Gy-1 each of which starts from a vertex in the first level of Gy-1 and ends at a vertex in its last level. We will argue that these paths must induce at least |Cy-1 | pairs as in the statement of the lemma. Any such path must use an edge (w, x) where w Li-1 and x Li followed by an edge (y , z ) where y Lk and z Lk+1 . For each path we fix one such quadruple (w, x, y , z ) and say that the path uses edges (w, x) and (y , z ) and "connection" (x, y ). Fix a connection (x, y ) that is used by some path. Let S1 (resp. S2 ) be the set of all vertices w Li-1 (resp. z Lk+1 ) such that some path uses edge (w, x) (resp. (y , z )). Let P1 (resp. P2 ) be the set of all paths that use edge (w, x) (resp. (y , z )) for some w S1 (resp. z S2 ). Note that |S1 | = |P1 | and |S2 | = |P2 | because the paths are edge-disjoint. We "generate" the set of pairs {(w, y ) | w S1 } {(x, z ) | z S2 }. = From the key lemma, it is evident that a cut of the nature described in step 2(a) in the algorithm can be found. Hence the size of C is given by: i ni 1 |(Gi , Ci )| |C | = |Ci | = O( 2 log2 ) l l i |(Gi , Ci )| n2 since each pair (u, v ) of vertices But contributes to at most one of the (Gi , Ci ). Therefore: |C | = O( n2 n log2 ) 2 l l Remark 3.1. Following Remark 2.1, we can improve 2 the bound on |C | to O( n2 log n ) for l log n. This l l implies that the greedy algorithm is an O(n2/3 log1/3 n) approximation for the EDP problem. For the case of undirected graphs, we can show a bound of O(n2 /l2 ) on the size of C in Theorem 1.1. It is easy to see that (u v )Gy-1 for each generated pair (u, v ). We delete the set of paths P1 P2 and the vertices References x and y . Note that the vertices x or y do not figure in any quadruple for the remaining paths. We have deleted [1] Chandra Chekuri and Sanjeev Khanna. Edge Disjoint at most |P1 | + |P2 | paths but have generated |P1 | + |P2 | Paths Revisited. In Proc. Symp. On Disc. Algorithms, 2003, pp. 628­637. pairs. By inductively repeating the argument on the [2] V. Guruswami, S. Khanna, B. Shepherd, R. Ra jararemaining paths, the claim follows. From the claim, it is easy to see that the number of pairs (u, v ) such that (u v )Gy-1 , u Li for some (y - 1) l/8 i < y l/8, and v Lk for some l - y l/8 < k l - (y - 1) l/8 is (|Cy-1 | 2l2 ). It is also easy to check that each such pair is in (G, Cy ). Remark 2.1. A more careful argument shows that the number of pairs in (G, Cy ) is (|Cy-1 | l2 ). This improves the bound in the Lemma to (1/l 2 ) log(n/l). 3 Main Theorem This section uses Lemma 2.1 to prove Theorem 1.1. If l log n, we can remove all the edges and still man and M. Yannakakis. Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. Proceedings of 31st STOC, 1999, pp. 19­28. [3] J. M. Kleinberg. Approximation algorithms for disjoint paths problems. PhD thesis, MIT, Cambridge, MA, May 1996. [4] S. G. Kolliopoulos and C. Stein. Approximating disjoint-paths problem using greedy algorithms and Packing Integer Programs. IPCO, 1998, pp. 153­168. [5] A.Srinivasan. Improved approximations for edgedisjoint paths, unsplittable flow, and related routing problems. Proceedings of the 38th Symp. on Foundations of Comp. Sci., 1997, pp. 416-425. 380