Edge disjoint paths revisited

Chandra Chekuri, Sanjeev Khanna

Research output: Contribution to conferencePaperpeer-review

Abstract

The approximability of the maximum edge disjoint paths problem (EDP) in directed graphs was seemingly settled by the Ω(m1/2-ε)-hardness result of Guruswami et al. [10] and the O(√m) approximation achievable via both the natural LP relaxation [19] and the greedy algorithm [11, 12]. Here m is the number of edges in the graph. However, we observe that the hardness of approximation shown in [10] applies to sparse graphs and hence when expressed as a function of n, the number of vertices, only an Ω(n1/2-ε)-hardness follows. On the other hand, the O(√m)-approximation algorithms do not guarantee a sub-linear (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 natural LP relaxation: an Ω(√n) lower bound and an O(√m) upper bound. Motivated by this discrepancy in the upper and lower bounds we study algorithms for the EDP in directed and undirected graphs obtaining improved approximation ratios. We show that the greedy algorithm has an approximation ratio of O(min(n2/3, √m)) in undirected graphs and a ratio of O(min(n4/5, √m)) in directed graphs. For acyclic graphs we give an O(√n log n) approximation via LP rounding. These are the first sub-linear approximation ratios for EDP. Our results also extend to EDP with weights and to the unsplittable flow problem with uniform edge capacities.

Original languageEnglish (US)
Pages628-637
Number of pages10
StatePublished - 2003
Externally publishedYes
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998

Other

OtherConfiguralble Computing: Technology and Applications
Country/TerritoryUnited States
CityBoston, MA
Period11/2/9811/3/98

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Edge disjoint paths revisited'. Together they form a unique fingerprint.

Cite this