Document Open Access Logo

One-Face Shortest Disjoint Paths with a Deviation Terminal

Authors Yusuke Kobayashi , Tatsuya Terao

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.47.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Yusuke Kobayashi
  • Research Institute for Mathematical Sciences, Kyoto University, Japan
Tatsuya Terao
  • Research Institute for Mathematical Sciences, Kyoto University, Japan

Funding

Supported by JSPS KAKENHI Grant Numbers 18H05291 and 20K11692.

Cite AsGet BibTex

Yusuke Kobayashi and Tatsuya Terao. One-Face Shortest Disjoint Paths with a Deviation Terminal. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.47

Abstract

For an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • shortest disjoint paths
  • polynomial time algorithm
  • planar graph

Metrics

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

References

  1. Isolde Adler, Stavros G Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M Thilikos. Irrelevant vertices for the planar disjoint paths problem. Journal of Combinatorial Theory, Series B, 122:815-843, 2017. Google Scholar
  2. Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a geometric lens to find k disjoint shortest paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198, pages 26:1-26:14, 2021. Google Scholar
  3. Kristóf Bérczi and Yusuke Kobayashi. The directed disjoint shortest paths problem. In 25th Annual European Symposium on Algorithms (ESA 2017), volume 122, pages 13:1-13:13, 2017. Google Scholar
  4. Andreas Björklund and Thore Husfeldt. Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018), pages 1-19, 2018. Google Scholar
  5. Andreas Björklund and Thore Husfeldt. Shortest two disjoint paths in polynomial time. SIAM Journal on Computing, 48(6):1698-1710, 2019. Google Scholar
  6. Glencora Borradaile, Amir Nayyeri, and Farzad Zafarani. Towards single face shortest vertex-disjoint paths in undirected planar graphs. In 23rd Annual European Symposium on Algorithms (ESA 2015), pages 227-238. Springer, 2015. Google Scholar
  7. Éric Colin de Verdière and Alexander Schrijver. Shortest vertex-disjoint two-face paths in planar graphs. ACM Transactions on Algorithms, 7(2):1-12, 2011. Google Scholar
  8. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 197-206, 2013. Google Scholar
  9. Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. Shortest k-disjoint paths via determinants. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), volume 122, pages 19:1-19:21, 2018. Google Scholar
  10. Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics, 85(2):113-138, 1998. Google Scholar
  11. Jeff Erickson and Yipu Wang. Four shortest vertex-disjoint paths in planar graphs. preprint on webpage, October 2017. URL: http://jeffe.cs.illinois.edu/pubs/pdf/disjoint.pdf.
  12. Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111-121, 1980. Google Scholar
  13. András Frank. Packing paths, circuits, and cuts - a survey. In Paths, flows, and VLSI-layout, pages 47-100. Springer, 1990. Google Scholar
  14. Marinus Gottschau, Marcus Kaiser, and Clara Waldmann. The undirected two disjoint shortest paths problem. Operations Research Letters, 47(1):70-75, 2019. Google Scholar
  15. Hiroshi Hirai and Hiroyuki Namba. Shortest (A+B)-path packing via hafnian. Algorithmica, 80(8):2478-2491, 2018. Google Scholar
  16. Richard M Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45-68, 1975. Google Scholar
  17. Yusuke Kobayashi and Ryo Sako. Two disjoint shortest paths problem with non-negative edge length. Operations Research Letters, 47(1):66-69, 2019. Google Scholar
  18. Yusuke Kobayashi and Christian Sommer. On shortest disjoint paths in planar graphs. Discrete Optimization, 7(4):234-245, 2010. Google Scholar
  19. Mark R Kramer. The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Advances in Computing Research, 2:129-146, 1984. Google Scholar
  20. James R. Lee, Manor Mendel, and Mohammad Moharrami. A node-capacitated Okamura-Seymour theorem. Mathematical Programming, 153(2):381-415, 2015. Google Scholar
  21. Willian Lochet. A polynomial time algorithm for the k-disjoint shortest paths problem. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pages 169-178, 2021. Google Scholar
  22. James F Lynch. The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter, 5(3):31-36, 1975. Google Scholar
  23. Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the 19th Annual ACM symposium on Theory of Computing (STOC 1987), pages 345-354, 1987. Google Scholar
  24. Richard G Ogier, Vladislav Rutenburg, and Nachum Shacham. Distributed algorithms for computing shortest pairs of disjoint paths. IEEE Transactions on Information Theory, 39(2):443-455, 1993. Google Scholar
  25. Haruko Okamura. Multicommodity flows in graphs. Discrete Applied Mathematics, 6(1):55-62, 1983. Google Scholar
  26. Haruko Okamura and Paul D Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B, 31(1):75-81, 1981. Google Scholar
  27. Neil Robertson and Paul D Seymour. Graph minors. VI. Disjoint paths across a disc. Journal of Combinatorial Theory, Series B, 41(1):115-138, 1986. Google Scholar
  28. Neil Robertson and Paul D Seymour. Graph minors. VII. Disjoint paths on a surface. Journal of Combinatorial Theory, Series B, 45(2):212-254, 1988. Google Scholar
  29. Neil Robertson and Paul D Seymour. Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995. Google Scholar
  30. Alexander Schrijver. Finding k disjoint paths in a directed planar graph. SIAM Journal on Computing, 23(4):780-788, 1994. Google Scholar
  31. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. Google Scholar
  32. Paul D. Seymour. Disjoint paths in graphs. Discrete Mathematics, 29:293-309, 1980. Google Scholar
  33. Yossi Shiloach. A polynomial solution to the undirected two paths problem. Journal of the ACM, 27(3):445-456, 1980. Google Scholar
  34. Anand Srinivas and Eytan Modiano. Finding minimum energy disjoint paths in wireless ad-hoc networks. Wireless Networks, 11(4):401-417, 2005. Google Scholar
  35. Richard P Stanley. Catalan Numbers. Cambridge University Press, 2015. Google Scholar
  36. Carsten Thomassen. 2-linked graphs. European Journal of Combinatorics, 1:371-378, 1980. 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 Imprint Privacy Contact