License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.15
URN: urn:nbn:de:0030-drops-60378
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6037/
Go to the corresponding LIPIcs Volume Portal


Ene, Alina ; Mnich, Matthias ; Pilipczuk, Marcin ; Risteski, Andrej

On Routing Disjoint Paths in Bounded Treewidth Graphs

pdf-format:
LIPIcs-SWAT-2016-15.pdf (0.6 MB)


Abstract

We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph G and a collection of k source-destination pairs M = (s_1, t_1), ..., (s_k, t_k). The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset M' of the pairs is a collection P of paths such that, for each pair (s_i, t_i) in M', there is a path in P connecting s_i to t_i. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph G has capacities cap(e) on the edges and a routing P is feasible if each edge e is in at most cap(e) of the paths of P. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP.

In this paper we obtain an O(r^3) approximation for MaxEDP on graphs of treewidth at most r and a matching approximation for MaxNDP on graphs of pathwidth at most r. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an O(r * 3^r) approximation for MaxEDP.

BibTeX - Entry

@InProceedings{ene_et_al:LIPIcs:2016:6037,
  author =	{Alina Ene and Matthias Mnich and Marcin Pilipczuk and Andrej Risteski},
  title =	{{On Routing Disjoint Paths in Bounded Treewidth Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6037},
  URN =		{urn:nbn:de:0030-drops-60378},
  doi =		{10.4230/LIPIcs.SWAT.2016.15},
  annote =	{Keywords: Algorithms and data structures, disjoint paths, treewidth}
}

Keywords: Algorithms and data structures, disjoint paths, treewidth
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI