Document Open Access Logo

Routing with Congestion in Acyclic Digraphs

Authors Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.7.pdf
  • Filesize: 0.53 MB
  • 11 pages

Document Identifiers

Author Details

Saeed Akhoondian Amiri
Stephan Kreutzer
Dániel Marx
Roman Rabinovich

Cite As Get BibTex

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.7

Abstract

We study the version of the k-disjoint paths problem where k demand pairs (s_1,t_1), ..., (s_k,t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths.  We show that on directed acyclic graphs the problem is solvable in time n^{O(d)} if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d*log(d))} for any computable function f.

Subject Classification

Keywords
  • algorithms
  • disjoint paths
  • congestion
  • acyclic digraphs
  • XP
  • W[1]-hard

Metrics

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

References

  1. Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, and Sebastian Siebertz. Vertex disjoint paths in upward planar graphs. In Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Éric Pin, and Nikolay K. Vereshchagin, editors, Computer Science - Theory and Applications: 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings, pages 52-64. Springer International Publishing, Cham, 2014. URL: http://dx.doi.org/10.1007/978-3-319-06686-8_5.
  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, 2011. URL: http://dx.doi.org/10.1007/s00493-010-2455-9.
  3. Jorgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications. Springer, 2nd edition, 2010. Google Scholar
  4. Parinya Chalermsook, Julia Chuzhoy, Alina Ene, and Shi Li. Approximation algorithms and hardness of integral concurrent flow. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 689-708, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214040.
  5. C. Chekuri, S. Khanna, and F. B. Shepherd. Edge-disjoint paths in planar graphs. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 71-80, Oct 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.27.
  6. Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 326-341. SIAM, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.24.
  7. Chandra Chekuri and Alina Ene. The all-or-nothing flow problem in directed graphs with symmetric demand pairs. In Jon Lee and Jens Vygen, editors, Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, volume 8494 of Lecture Notes in Computer Science, pages 222-233. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07557-0_19.
  8. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. Multicommodity flow, well-linked terminals, and routing problems. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05, pages 183-192, New York, NY, USA, 2005. ACM. URL: http://dx.doi.org/10.1145/1060590.1060618.
  9. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An o(√ n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137-146, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a007.
  10. J. Chuzhoy and S. Li. A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 233-242, Oct 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.54.
  11. M. Cygan, D. Marx, M. Pilipczuk, and M. Pilipczuk. The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 197-206, Oct 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.29.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  13. Reinhard Diestel. Graph Theory. Springer-Verlag, 4th edition, 2010. Google Scholar
  14. S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976. Google Scholar
  15. Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 - 121, 1980. URL: http://www.sciencedirect.com/science/article/pii/0304397580900092, URL: http://dx.doi.org/http://dx.doi.org/10.1016/0304-3975(80)90009-2.
  16. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. System Sci., 63(4):512-530, 2001. Google Scholar
  17. Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. Directed tree-width. J. Comb. Theory, Ser. B, 82(1):138-154, 2001. Google Scholar
  18. G. Stavros Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99(1):63-87, 2003. URL: http://dx.doi.org/10.1007/s10107-002-0370-6.
  19. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.
  20. Dániel Marx. Can you beat treewidth? Theory of Computing, 6(1):85-112, 2010. http://arxiv.org/abs/toc:v006/a005, URL: http://dx.doi.org/10.4086/toc.2010.v006a005.
  21. N. Robertson and P. D. Seymour. Graph minors I - XXIII, 1982 - 2010. Appearing in Journal of Combinatorial Theory, Series B., from 1982-2010. Google Scholar
  22. Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math., 24(1):146-157, 2010. URL: http://dx.doi.org/10.1137/070697781.
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