Maximum edge-disjoint paths in k-sums of graphs

Chandra Chekuri, Guyslain Naves, F. Bruce Shepherd

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow based relaxation for it. The integrality gap is known to be Ω(√n) even for planar graphs [11] due to a simple topological obstruction and a major focus, following earlier work [14], has been understanding the gap if some constant congestion is allowed. In planar graphs the integrality gap is O(1) with congestion 2 [19,5]. In general graphs, recent work has shown the gap to be O(polylog(n)) [8,9] with congestion 2. Moreover, the gap is Ω(logΩ(c) n) in general graphs with congestion c for any constant c ≥ 1 [1]. It is natural to ask for which classes of graphs does a constant-factor constant-congestion property hold. It is easy to deduce that for given constant bounds on the approximation and congestion, the class of "nice" graphs is minor-closed. Is the converse true? Does every proper minor-closed family of graphs exhibit a constant-factor constant-congestion bound relative to the LP relaxation? We conjecture that the answer is yes. One stumbling block has been that such bounds were not known for bounded treewidth graphs (or even treewidth 3). In this paper we give a polytime algorithm which takes a fractional routing solution in a graph of bounded treewidth and is able to integrally route a constant fraction of the LP solution's value. Note that we do not incur any edge congestion. Previously this was not known even for series parallel graphs which have treewidth 2. The algorithm is based on a more general argument that applies to k-sums of graphs in some graph family, as long as the graph family has a constant-factor constant-congestion bound. We then use this to show that such bounds hold for the class of k-sums of bounded genus graphs.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Number of pages12
EditionPART 1
StatePublished - 2013
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: Jul 8 2013Jul 12 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Maximum edge-disjoint paths in k-sums of graphs'. Together they form a unique fingerprint.

Cite this