Document Open Access Logo

Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Authors Andreas Björklund, Petteri Kaski, Ioannis Koutis



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.91.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Björklund
Petteri Kaski
Ioannis Koutis

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 91:1-91:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.91

Abstract

We are motivated by a tantalizing open question in exact algorithms: can we detect whether an n-vertex directed graph G has a Hamiltonian cycle in time significantly less than 2^n? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0<lambda<1 and prime p we can count the Hamiltonian cycles modulo p^((1-lambda)n/(3p)) in expected time less than c^n for a constant c<2 that depends only on p and lambda. Such an algorithm was previously known only for the case of counting modulo two [Bj\"orklund and Husfeldt, FOCS 2013]. 2. We show that we can detect a Hamiltonian cycle in O^*(3^(n-alpha(G))) time and polynomial space, where alpha(G) is the size of the maximum independent set in G. In particular, this yields an O^*(3^(n/2)) time algorithm for bipartite directed graphs, which is faster than the exponential-space algorithm in [Cygan et al., STOC 2013]. Our algorithms are based on the algebraic combinatorics of "incidence assignments" that we can capture through evaluation of determinants of Laplacian-like matrices, inspired by the Matrix--Tree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the Matrix--Tree Theorem to derive simple algebraic algorithms for detecting out-branchings. Specifically, we give an O^*(2^k)-time randomized algorithm for detecting out-branchings with at least k internal vertices, improving upon the algorithms of [Zehavi, ESA 2015] and [Bj\"orklund et al., ICALP 2015]. We also present an algebraic algorithm for the directed k-Leaf problem, based on a non-standard monomial detection problem.
Keywords
  • counting
  • directed Hamiltonicity
  • graph Laplacian
  • independent set
  • k-internal out-branching

Metrics

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

References

  1. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61-63, January 1962. URL: http://dx.doi.org/10.1145/321105.321111.
  2. Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18:147-150, 1984. URL: http://dx.doi.org/10.1016/0020-0190(84)90018-8.
  3. Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM Journal on Computing, 43(1):280-299, 2014. URL: http://dx.doi.org/10.1137/110839229.
  4. Andreas Björklund. Below All Subsets for Some Permutational Counting Problems . In Rasmus Pagh, editor, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:11, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.17.
  5. Andreas Björklund, Holger Dell, and Thore Husfeldt. The parity of set systems under random restrictions with applications to exponential time problems. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 231-242, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_19.
  6. Andreas Björklund and Thore Husfeldt. The parity of directed hamiltonian cycles. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 724-735, Oct 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.83.
  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, April 2012. URL: http://dx.doi.org/10.1145/2151171.2151181.
  8. Andreas Björklund, Thore Husfeldt, and Isak Lyckberg. Computing the permanent modulo a prime power. Unpublished manuscript, 2015. Google Scholar
  9. Andreas Björklund, Vikram Kamat, Lukasz Kowalik, and Meirav Zehavi. Spotting trees with few leaves. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 243-255. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_20.
  10. Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. CoRR, abs/1607.04002, 2017. URL: http://arxiv.org/abs/1607.04002.
  11. Andreas Björklund, Petteri Kaski, and Łukasz Kowalik. Constrained multilinear detection and generalized graph motifs. Algorithmica, 74(2):947-967, 2016. URL: http://dx.doi.org/10.1007/s00453-015-9981-1.
  12. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC'13, pages 301-310, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2488608.2488646.
  13. Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree. Information and Computation, 243:75-85, 2015. 40th International Colloquium on Automata, Languages and Programming (ICALP 2013). URL: http://dx.doi.org/10.1016/j.ic.2014.12.007.
  14. R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7:193-195, 1978. Google Scholar
  15. Peter Floderus, Andrzej Lingas, Mia Persson, and Dzmitry Sledneu. Detecting monomials with k distinct variables. Information Processing Letters, 115(2):82-86, 2015. URL: http://dx.doi.org/10.1016/j.ipl.2014.07.003.
  16. Ariel Gabizon, Daniel Lokshtanov, and Michał Pilipczuk. Fast algorithms for parameterized problems with relaxed disjointness constraints. In Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 545-556, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_46.
  17. Ira M. Gessel and Richard P. Stanley. Algebraic enumeration. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume II, pages 1021-1061. North-Holland, Amsterdam, 1995. Google Scholar
  18. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  19. Richard M. Karp. Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters, 1(2):49-51, 1982. URL: http://dx.doi.org/10.1016/0167-6377(82)90044-X.
  20. Samuel Kohn, Allan Gottlieb, and Meryle Kohn. A generating function approach to the traveling salesman problem. In Proceedings of the Annual Conference (ACM'77), Association for Computing Machinery, pages 294-300, 1977. Google Scholar
  21. Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems. ACM Transactions on Algorithms, 12:Art. 31, 18, 2016. URL: http://dx.doi.org/10.1145/2885499.
  22. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27:701-717, 1980. Google Scholar
  23. Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, 3rd edition, 2013. Google Scholar
  24. Meirav Zehavi. Mixing color coding-related techniques. In Algorithms ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 1037-1049. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_86.
  25. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proc. International Symposium on Symbolic and Algebraic Computati on, volume 72 of Lecture Notes in Computer Science, pages 216-226, Berlin, 1979. Springer. 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