Document Open Access Logo

On Routing Disjoint Paths in Bounded Treewidth Graphs

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

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.15.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Alina Ene
Matthias Mnich
Marcin Pilipczuk
Andrej Risteski

Cite As Get BibTex

Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On Routing Disjoint Paths in Bounded Treewidth Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.15

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.

Subject Classification

Keywords
  • Algorithms and data structures
  • disjoint paths
  • treewidth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1 + ε)-approximate flow sparsifiers. In Proc. SODA 2014, pages 279-293, 2014. Google Scholar
  2. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang. Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5):485-520, 2010. Google Scholar
  3. Parinya Chalermsook, Julia Chuzhoy, Alina Ene, and Shi Li. Approximation algorithms and hardness of integral concurrent flow. In Proc. STOC 2012, pages 689-708, 2012. Google Scholar
  4. C. Chekuri, S. Khanna, and F.B. Shepherd. An O(√n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput., 2(7):137-146, 2006. Google Scholar
  5. Chandra Chekuri and Julia Chuzhoy. Large-treewidth graph decompositions and applications. In Proc. STOC 2013, pages 291-300, 2013. Google Scholar
  6. Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. SODA 2013, pages 326-341, 2013. Google Scholar
  7. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. Multicommodity flow, well-linked terminals, and routing problems. In Proc. STOC 2005, pages 183-192, 2005. Google Scholar
  8. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Comput., 39(1):281-301, 2009. Google Scholar
  9. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. A note on multiflows and treewidth. Algorithmica, 54(3):400-412, 2009. Google Scholar
  10. Chandra Chekuri, Guyslain Naves, and F. Bruce Shepherd. Maximum edge-disjoint paths in k-sums of graphs. In Proc. ICALP 2013, volume 7965 of LNCS, pages 328-339, 2013. Google Scholar
  11. Chandra Chekuri, Guyslain Naves, and F. Bruce Shepherd. Maximum edge-disjoint paths in k-sums of graphs. Technical report, ArXiv, 2013. URL: http://arxiv.org/abs/1303.4897.
  12. Eden Chlamtac, Robert Krauthgamer, and Prasad Raghavendra. Approximating sparsest cut in graphs of bounded treewidth. In Proc. APPROX-RANDOM 2010, volume 6302 of LNCS, pages 124-137, 2010. Google Scholar
  13. Julia Chuzhoy. On vertex sparsifiers with Steiner nodes. In Proc. STOC 2012, pages 673-688, 2012. Google Scholar
  14. Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In Proc. FOCS 2012, pages 233-242, 2012. Google Scholar
  15. Reinhard Diestel. Graph theory, volume 173. Springer, third edition, 2005. Google Scholar
  16. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997. Google Scholar
  17. Anupam Gupta, Kunal Talwar, and David Witmer. Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In Proc. STOC 2013, pages 281-290, 2013. Google Scholar
  18. R.M. Karp. On the computational complexity of combinatorial problems. Networks, 5:45-68, 1975. Google Scholar
  19. S.G. Kolliopoulos and C. Stein. Approximating disjoint-path problems using packing integer programs. Math. Prog., 99(1):63-87, 2004. Google Scholar
  20. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  21. Neil Robertson and Paul D Seymour. Graph minors. V. Excluding a planar graph. J. Combinatorial Theory, Ser. B, 41(1):92-114, 1986. Google Scholar
  22. Neil Robertson and Paul D Seymour. Graph minors. XIII. The disjoint paths problem. J. Combinatorial Theory, Ser. B, 63(1):65-110, 1995. Google Scholar
  23. Neil Robertson and Paul D Seymour. Graph minors. XVI. Excluding a non-planar graph. J. Combinatorial Theory, Ser. B, 89(1):43-76, 2003. Google Scholar
  24. Löc Séguin-Charbonneau and F Bruce Shepherd. Maximum edge-disjoint paths in planar graphs with congestion 2. In Proc. FOCS 2011, pages 200-209, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact