Document Open Access Logo

The Asymmetric Travelling Salesman Problem In Sparse Digraphs

Authors Łukasz Kowalik , Konrad Majewski

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.23.pdf
  • Filesize: 0.64 MB
  • 18 pages

Document Identifiers

Author Details

Łukasz Kowalik
  • Institute of Informatics, University of Warsaw, Poland
Konrad Majewski
  • Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Poland

Funding

  • Kowalik, Łukasz: Supported by ERC Starting Grant TOTAL (Grant Agreement No 677651).

Acknowledgements

The authors thank the reviewers for careful reading and useful comments.

Cite AsGet BibTex

Łukasz Kowalik and Konrad Majewski. The Asymmetric Travelling Salesman Problem In Sparse Digraphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.IPEC.2020.23

Abstract

Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time 𝒪^*(2ⁿ) developed almost 60 years ago by Bellman, Held and Karp, is still the state of the art for both of these problems. In this work we focus on sparse digraphs. First, we recall known approaches for Undirected Hamiltonicity and TSP in sparse graphs and we analyse their consequences for Directed Hamiltonicity and ATSP in sparse digraphs, either by adapting the algorithm, or by using reductions. In this way, we get a number of running time upper bounds for a few classes of sparse digraphs, including 𝒪^*(2^(n/3)) for digraphs with both out- and indegree bounded by 2, and 𝒪^*(3^(n/2)) for digraphs with outdegree bounded by 3. Our main results are focused on digraphs of bounded average outdegree d. The baseline for ATSP here is a simple enumeration of cycle covers which can be done in time bounded by 𝒪^*(μ(d)ⁿ) for a function μ(d) ≤ (⌈d⌉!)^(1/⌈d⌉). One can also observe that Directed Hamiltonicity can be solved in randomized time 𝒪^*((2-2^(-d))ⁿ) and polynomial space, by adapting a recent result of Björklund [ISAAC 2018] stated originally for Undirected Hamiltonicity in sparse bipartite graphs. We present two new deterministic algorithms for ATSP: the first running in time 𝒪(2^(0.441(d-1)n)) and polynomial space, and the second in exponential space with running time of 𝒪^*(τ(d)^(n/2)) for a function τ(d) ≤ d.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • asymmetric traveling salesman problem
  • Hamiltonian cycle
  • sparse graphs
  • exponential algorithm

Metrics

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

Related Versions

References

  1. Eric T. Bax. Inclusion and exclusion algorithm for the Hamiltonian path problem. Inf. Process. Lett., 47(4):203–207, September 1993. URL: https://doi.org/10.1016/0020-0190(93)90033-6.
  2. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61–63, January 1962. URL: https://doi.org/10.1145/321105.321111.
  3. Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. URL: https://doi.org/10.1137/110839229.
  4. Andreas Björklund. Exploiting sparsity for bipartite hamiltonicity. In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors, 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:11, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.3.
  5. Andreas Björklund. An asymptotically fast polynomial space algorithm for hamiltonicity detection in sparse directed graphs, 2020. URL: http://arxiv.org/abs/2009.11780.
  6. Andreas Björklund and Thore Husfeldt. The parity of directed Hamiltonian cycles. In FOCS, pages 727-735. IEEE Computer Society, 2013. Google Scholar
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms, 8(2):18:1-18:13, 2012. URL: https://doi.org/10.1145/2151171.2151181.
  8. Andreas Björklund, Vikram Kamat, Lukasz Kowalik, and Meirav Zehavi. Spotting trees with few leaves. SIAM J. Discret. Math., 31(2):687-713, 2017. URL: https://doi.org/10.1137/15M1048975.
  9. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed hamiltonicity and out-branchings via generalized laplacians. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 91:1-91:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.91.
  10. Andreas Björklund and Ryan Williams. Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 25: 1-25: 14. Schloss Dagstuhl - Leibniz Center for Computer Science, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.25.
  11. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  12. Lev Meerovich Brègman. Some properties of nonnegative matrices and their permanents. Doklady Akademii Nauk, 211(1):27-30, 1973. Google Scholar
  13. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. J. ACM, 65(3), March 2018. URL: https://doi.org/10.1145/3148227.
  14. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150-159. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.23.
  15. Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput., 243:75-85, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.007.
  16. David Eppstein. The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl., 11(1):61-81, 2007. URL: https://doi.org/10.7155/jgaa.00137.
  17. Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. On two techniques of combining branching and treewidth. Algorithmica, 54(2):181-207, 2009. URL: https://doi.org/10.1007/s00453-007-9133-3.
  18. Komei Fukuda and Tomomi Matsui. Finding all the perfect matchings in bipartite graphs. Applied Mathematics Letters, 7(1):15-18, 1994. Google Scholar
  19. Heidi Gebauer. How many Hamilton cycles and perfect matchings are there? Master’s thesis, ETH Zürich, March 2007. Google Scholar
  20. Heidi Gebauer. On the number of Hamilton cycles in bounded degree graphs. In Robert Sedgewick and Wojciech Szpankowski, editors, Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2008, San Francisco, California, USA, January 19, 2008, pages 241-248. SIAM, 2008. URL: https://doi.org/10.1137/1.9781611972986.8.
  21. Heidi Gebauer. Finding and enumerating Hamilton cycles in 4-regular graphs. Theor. Comput. Sci., 412(35):4579-4591, 2011. URL: https://doi.org/10.1016/j.tcs.2011.04.038.
  22. Yuri Gurevich and Saharon Shelah. Expected computation time for Hamiltonian path problem. SIAM J. Comput., 16(3):486–502, June 1987. URL: https://doi.org/10.1137/0216034.
  23. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM National Meeting, ACM ’61, page 71.201–71.204, New York, NY, USA, 1961. Association for Computing Machinery. URL: https://doi.org/10.1145/800029.808532.
  24. Richard M. Karp. Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett., 1(2):49–51, April 1982. URL: https://doi.org/10.1016/0167-6377(82)90044-X.
  25. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discret. Math., 23(1):407-427, 2009. URL: https://doi.org/10.1137/080715482.
  26. Samuel Kohn, Allan Gottlieb, and Meryle Kohn. A generating function approach to the traveling salesman problem. In Proceedings of the 1977 Annual Conference, ACM ’77, page 294–300, New York, NY, USA, 1977. Association for Computing Machinery. URL: https://doi.org/10.1145/800179.810218.
  27. Łukasz Kowalik and Konrad Majewski. The asymmetric travelling salesman problem in sparse digraphs, 2020. URL: http://arxiv.org/abs/2007.12120.
  28. Jesper Nederlof. Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 40-53. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384264.
  29. Mohd Shahrizan Othman, Aleksandar Shurbevski, and Hiroshi Nagamochi. Polynomial-space exact algorithms for the bipartite traveling salesman problem. IEICE Trans. Inf. Syst., 101-D(3):611-612, 2018. URL: https://doi.org/10.1587/transinf.2017FCL0003.
  30. Ján Plesník. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett., 8(4):199-201, 1979. URL: https://doi.org/10.1016/0020-0190(79)90023-1.
  31. Frank Rubin. A search procedure for Hamilton paths and circuits. J. ACM, 21(4):576–580, October 1974. URL: https://doi.org/10.1145/321850.321854.
  32. Alexander Schrijver. A short proof of Minc’s conjecture. Journal of combinatorial theory, Series A, 25(1):80-83, 1978. Google Scholar
  33. Mingyu Xiao and Hiroshi Nagamochi. An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. Algorithmica, 74(2):713-741, 2016. URL: https://doi.org/10.1007/s00453-015-9970-4.
  34. Mingyu Xiao and Hiroshi Nagamochi. An improved exact algorithm for TSP in graphs of maximum degree 4. Theory Comput. Syst., 58(2):241-272, 2016. URL: https://doi.org/10.1007/s00224-015-9612-x.
  35. Norhazwani Md Yunos, Aleksandar Shurbevski, and Hiroshi Nagamochi. An improved-time polynomial-space exact algorithm for TSP in degree-5 graphs. J. Inf. Process., 25:639-654, 2017. URL: https://doi.org/10.2197/ipsjjip.25.639.
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