Document Open Access Logo

Exploiting Sparsity for Bipartite Hamiltonicity

Author Andreas Björklund

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.3.pdf
  • Filesize: 407 kB
  • 11 pages

Document Identifiers

Author Details

Andreas Björklund
  • Department of Computer Science, Lund University, Sweden

Funding

This work was supported in part by the Swedish Research Council grant VR-2016-03855, "Algebraic Graph Algorithms".

Cite As Get BibTex

Andreas Björklund. Exploiting Sparsity for Bipartite Hamiltonicity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.3

Abstract

We present a Monte Carlo algorithm that detects the presence of a Hamiltonian cycle in an n-vertex undirected bipartite graph of average degree delta >= 3 almost surely and with no false positives, in (2-2^{1-delta})^{n/2}poly(n) time using only polynomial space. With the exception of cubic graphs, this is faster than the best previously known algorithms. Our method is a combination of a variant of Björklund's 2^{n/2}poly(n) time Monte Carlo algorithm for Hamiltonicity detection in bipartite graphs, SICOMP 2014, and a simple fast solution listing algorithm for very sparse CNF-SAT formulas.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Hamiltonian cycle
  • bipartite graph

Metrics

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

References

  1. Andreas Björklund. Determinant Sums for Undirected Hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. URL: http://dx.doi.org/10.1137/110839229.
  2. Andreas Björklund and Thore Husfeldt. The Parity of Directed Hamiltonian Cycles. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 727-735, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.83.
  3. 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: http://dx.doi.org/10.1145/2151171.2151181.
  4. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 91:1-91:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.91.
  5. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM, 65(3):12:1-12:46, 2018. Google Scholar
  6. 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 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 150-159. IEEE Computer Society, 2011. Google Scholar
  7. Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree. Inf. Comput., 243:75-85, 2015. Google Scholar
  8. Richard A. DeMillo and Richard J. Lipton. A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett., 7(4):193-195, 1978. Google Scholar
  9. David Eppstein. The Traveling Salesman Problem for Cubic Graphs. J. Graph Algorithms Appl., 11(1):61-81, 2007. Google Scholar
  10. Fedor V. Fomin and Kjartan Høie. Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett., 97(5):191-196, 2006. Google Scholar
  11. Kazuo Iwama and Takuya Nakashima. An Improved Exact Algorithm for Cubic Graph TSP. In COCOON, volume 4598 of Lecture Notes in Computer Science, pages 108-117. Springer, 2007. Google Scholar
  12. Richard M. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  13. 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. Discrete Math., 23(1):407-427, 2009. Google Scholar
  14. Marko Samer and Stefan Szeider. Algorithms for propositional model counting. J. Discrete Algorithms, 8(1):50-64, 2010. Google Scholar
  15. Jacob T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  16. Andrew G. Thomason. Hamiltonian Cycles and Uniquely Edge Colourable Graphs. In B. Bollobás, editor, Advances in Graph Theory, volume 3 of Annals of Discrete Mathematics, pages 259-268. Elsevier, 1978. Google Scholar
  17. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. Google Scholar
  18. Leslie G. Valiant. Completeness for Parity Problems. In COCOON, volume 3595 of Lecture Notes in Computer Science, pages 1-8. Springer, 2005. 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