Edge-disjoint paths in planar graphs

C. Chekuri, S. Khanna, F. B. Shepherd

Research output: Contribution to journalConference articlepeer-review

Abstract

We study the maximum edge-disjoint paths problem (MEDP). We are given a graph G = (V, E) and a set T = {s 1t 1, s 2t 2, ...,s kt k} of pairs of vertices: the objective is to find the maximum number of pairs in T that can be connected via edge-disjoint paths. Our main result is a poly-logarithmic approximation for MEDP on undirected planar graphs if a congestion of 2 is allowed, that is, we allow up to 2 paths to share an edge. Prior to our work, for any constant congestion, only a polynomial-factor approximation was known for planar graphs although much stronger results are known for some special cases such as grids and grid-like graphs. We note that the natural multi-commodity flow relaxation of the problem has an integrality gap Ω(√|V|) even on planar graphs when no congestion is allowed. Our starting point is the same relaxation and our result implies that the integrality gap shrinks to a poly-logarithmic factor once 2 paths are allowed per edge. Our result also extends to the unsplittable flow problem and the maximum integer multicommodity flow problem. A set X ⊆ V is well-linked if for each S ⊂ V, |δ(S)| ≥ min{|S ∩ X|, |(V - S) D X|}. The heart of our approach is to show that in any undirected planar graph, given any matching M on a well-linked set X, we can route Ω(|M|) pairs in M with a congestion of 2. Moreover, all pairs in M can be routed with constant congestion for a sufficiently large constant. This results also yields a different proof of a theorem of Klein, Plotkin, and Rao that shows an O(1) maxflow-mincut gap for uniform multicommodity flow instances in planar graphs. The framework developed in this paper applies to general graphs as well. If a certain graph theoretic conjecture is true, it will yield poly-logarithmic integrality gap for MEDP with constant congestion.

Original languageEnglish (US)
Pages (from-to)71-80
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 2004
Externally publishedYes
EventProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy
Duration: Oct 17 2004Oct 19 2004

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Edge-disjoint paths in planar graphs'. Together they form a unique fingerprint.

Cite this