Edge-disjoint paths revisited

ABSTRACT

The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an Ω(m^1/2 − &epsis;)-hardness result of Guruswami et al. [2003], and an O(&sqrt;m) approximation achievable via a natural multicommodity-flow-based LP relaxation as well as a greedy algorithm. Here m is the number of edges in the graph. We observe that the Ω(m^1/2 − &epsis;)-hardness of approximation applies to sparse graphs, and hence when expressed as a function of n, that is, the number of vertices, only an Ω(n^1/2− &epsis;)-hardness follows. On the other hand, O(&sqrt;m)-approximation algorithms do not guarantee a sublinear (in terms of n) approximation algorithm for dense graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an Ω(&sqrt;n) lower bound and O(&sqrt;m) upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of O(min(n^2/3, &sqrt;m)) in undirected graphs and a ratio of O(min(n^4/5, &sqrt;m)) in directed graphs. For acyclic graphs we give an O(&sqrt;n ln n) approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP).

REFERENCES

• 1: Azar, Y., and Regev, O. 2006. Combinatorial algorithms for the unsplittable flow problem. Algorithmica 44, 1, 49--66.
• 2: Alok Baveja , Aravind Srinivasan, Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems, Mathematics of Operations Research, v.25 n.2, p.255-280, May 2000 [doi>10.1287/moor.25.2.255.12228]
• 3: Chekuri, C., Khanna, S., and Shepherd, F. B. 2006. An O(&sqrt;n) Approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2, 7, 137--146.
• 4: Joseph Cheriyan , Howard Karloff , Yuval Rabani†, Approximating Directed Multicuts, Combinatorica, v.25 n.3, p.251-269, May 2005 [doi>10.1007/s00493-005-0015-5]
• 5: Even, S., and Tarjan, R. 1975. Network flow and testing graph connectivity. SIAM J. Comput. 4, 507-518.
• 6: Fortune, S., Hopcroft, J., and Wyllie, J. 1980. The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 2, 111--121.
• 7: Frank, A. 1990. Packing paths, cuts, and circuits---A survey. In Paths, Flows and VLSI-Layout, B. Korte et al., eds., Springer, 49--100.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 10: Garg, N., Vazirani, V. V., and Yannakakis, M. 1997. Primal-Dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18, 3--20.
• 11: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Journal of Computer and System Sciences, v.67 n.3, p.473-496, November 2003 [doi>10.1016/S0022-0000(03)00066-7]
• 12: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, Massachusetts Institute of Technology, 1996
• 13: Stavros G. Kolliopoulos , Clifford Stein, Exact and approximation algorithms for network flow and disjoint-path problems, Dartmouth College, Hanover, NH, 1998
• 14: Kolliopoulos, S. G., and Stein, C. 2004. Approximating disjoint-path problems using packing integer programs. Math. Program. Ser. A 99, 63--87.
• 15: Petr Kolman, A note on the greedy algorithm for the unsplittable flow problem, Information Processing Letters, v.88 n.3, p.101-105, 15 November 2003 [doi>10.1016/S0020-0190(03)00351-X]
• 16: Lawler, E. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, Austin, TX.
• 17: Bin Ma , Lusheng Wang, On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints, Journal of Computer and System Sciences, v.60 n.1, p.1-12, Feb. 2000 [doi>10.1006/jcss.1999.1661]
• 18: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 19: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 20: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 21: Robertson, N., and Seymour, P. 1990. Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout, B. Korte et al., eds. Springer.
• 22: Alexander Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 23: A. Srinivasan, Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.416, October 19-22, 1997
• 24: Kasturi Varadarajan , Ganesh Venkataraman, Graph decomposition and a greedy algorithm for edge-disjoint paths, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 25: West, D. B. 1996. Introduction to Graph Theory. Prentice-Hall.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
Edge-disjoint paths, approximation algorithm, greedy algorithm, multicommodity flow relaxation