Document Open Access Logo

Shortest k-Disjoint Paths via Determinants

Authors Samir Datta, Siddharth Iyer, Raghav Kulkarni, Anish Mukherjee

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.19.pdf
  • Filesize: 0.85 MB
  • 21 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute and UMI ReLaX, Chennai, India
Siddharth Iyer
  • University of Washington, Seattle, USA
Raghav Kulkarni
  • Chennai Mathematical Institute, Chennai, India
Anish Mukherjee
  • Chennai Mathematical Institute, Chennai, India

Funding

  • Datta, Samir: The author was partially funded by a grant from Infosys foundation and SERB grant MTR/2017/000480.
  • Iyer, Siddharth: The work was done while the author was a student at Birla Institute of Technology and Science, India.
  • Mukherjee, Anish: The author was partially supported by a grant from Infosys foundation and TCS PhD fellowship.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.19

Abstract

The well-known k-disjoint path problem (k-DPP) asks for pairwise vertex-disjoint paths between k specified pairs of vertices (s_i, t_i) in a given graph, if they exist. The decision version of the shortest k-DPP asks for the length of the shortest (in terms of total length) such paths. Similarly, the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest k-DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdière and Schrijver [Éric Colin de Verdière and Alexander Schrijver, 2011] for the general one-face problem. We do so by providing a randomised NC^2 algorithm along with an O(n^{omega/2}) time randomised sequential algorithm, for any fixed k. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. The algorithms are based on a bijection between a shortest k-tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "pure" cycle covers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
Keywords
  • disjoint paths
  • planar graph
  • parallel algorithm
  • cycle cover
  • determinant
  • inclusion-exclusion

Metrics

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

Related Versions

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. Eric Allender and Meena Mahajan. The complexity of planarity testing. Inf. Comput., 189(1):117-134, 2004. Google Scholar
  3. Andreas Björklund and Thore Husfeldt. Shortest Two Disjoint Paths in Polynomial Time. In Automata, Languages, and Programming - 41st International Colloquium, ICALP, Proceedings, Part I, pages 211-222, 2014. 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. Google Scholar
  5. 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, pages 227-238, 2015. Google Scholar
  6. Jin-yi Cai and D. Sivakumar. Resolution of Hartmanis' conjecture for NL-hard sparse sets. Theor. Comput. Sci., 240(2):257-269, 2000. Google Scholar
  7. Julia Chuzhoy, David H. K. Kim, and Shi Li. Improved Approximation for Node-disjoint Paths in Planar Graphs. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC 2016, pages 556-569. ACM, 2016. Google Scholar
  8. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. New Hardness Results for Routing on Disjoint Paths. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 86-99. ACM, 2017. Google Scholar
  9. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pages 38:1-38:14, 2018. Google Scholar
  10. L. Csanky. Fast Parallel Matrix Inversion Algorithms. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, SFCS '75, pages 11-12, 1975. Google Scholar
  11. C. Damm. DET=L^(#L). Technical Report Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universität zu Berlin, 1991. Google Scholar
  12. Samir Datta and Gautam Prakriya. Planarity Testing Revisited. In Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings, pages 540-551, 2011. Google Scholar
  13. Éric Colin de Verdière and Alexander Schrijver. Shortest vertex-disjoint two-face paths in planar graphs. ACM Transactions on Algorithms, 7(2):19, 2011. Google Scholar
  14. Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathematics, 85(2):113-138, 1998. Google Scholar
  15. Jeff Erickson and Yipu Wang. Four Shortest Vertex-disjoint Paths in Planar Graphs. preprint on webpage, October 2017. (retrieved April, 2018). URL: http://jeffe.cs.illinois.edu/pubs/pdf/disjoint.pdf.
  16. Steven Fortune, John E. Hopcroft, and James Wyllie. The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci., pages 111-121, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90009-2.
  17. C. Hernando, F. Hurtado, and Marc Noy. Graphs of Non-Crossing Perfect Matchings. Graphs and Combinatorics, 18(3):517-532, 2002. Google Scholar
  18. Richard M. Karp. On the computational complexity of combinatorial problems. Networks, 5:45-68, 1975. Google Scholar
  19. Yusuke Kobayashi and Christian Sommer. On Shortest Disjoint Paths in Planar Graphs. Discret. Optim., 7(4):234-245, November 2010. Google Scholar
  20. James F. Lynch. The Equivalence of Theorem Proving and the Interconnection Problem. SIGDA Newsl., 5(3):31-36, September 1975. Google Scholar
  21. Meena Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sci., 1997, 1997. URL: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html.
  22. Matthias Middendorf and Frank Pfeiffer. On the complexity of the disjoint paths problems. Combinatorica, 13(1):97-107, 1993. Google Scholar
  23. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. Google Scholar
  24. Neil Robertson and Paul D. Seymour. Graph minors. VI. Disjoint paths across a disc. J. Comb. Theory, Ser. B, 41(1):115-138, 1986. Google Scholar
  25. Neil Robertson and Paul D. Seymour. Graph minors. VII. Disjoint paths on a surface. J. Comb. Theory, Ser. B, 45(2):212-254, 1988. Google Scholar
  26. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. Google Scholar
  27. Petra Scheffler. A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical Report 396, 1994. Google Scholar
  28. Alexander Schrijver. Finding k Disjoint Paths in a Directed Planar Graph. SIAM J. Comput., 23(4):780-788, 1994. Google Scholar
  29. Werner Schwärzler. On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary. Combinatorica, 29(1):121-126, 2009. Google Scholar
  30. Hitoshi Suzuki, Takehiro Akama, and Takao Nishizeki. Finding Steiner Forests in Planar Graphs. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '90, pages 444-453. SIAM, 1990. Google Scholar
  31. Hitoshi Suzuki, Chiseko Yamanaka, and Takao Nishizeki. Parallel Algorithms for Finding Steiner Forests in Planar Graphs. In Proceedings of the International Symposium on Algorithms, SIGAL '90, pages 458-467. Springer-Verlag, 1990. Google Scholar
  32. S. Toda. Counting Problems Computationally Equivalent to the Determinant. Technical Report CSIM 91-07, Dept of Comp Sc &Information Mathematics, Univ of Electro-Communications, Chofu-shi, Tokyo, 1991. Google Scholar
  33. I. Tzameret. Studies in Algebraic and Propositional Proof Complexity. PhD thesis, Tel Aviv University, 2008. Google Scholar
  34. H. van der Holst and J.C. de Pina. Length-bounded disjoint paths in planar graphs. Discrete Applied Mathematics, 120(1):251-261, 2002. Google Scholar
  35. V. Vinay. Counting Auxiliary Pushdown Automata. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pages 270-284, 1991. Google Scholar
  36. Raphael Yuster. Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 137-145, 2008. 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