Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
(2017) 44th International Colloquium on Automata, Languages, and Programming p.1-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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1322b88d-f2ea-461c-a46f-225bd8aee829
- author
- Björklund, Andreas LU ; Kaski, Petteri and Koutis, Ioannis
- organization
- publishing date
- 2017-07-10
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
- article number
- 91
- pages
- 14 pages
- conference name
- 44th International Colloquium on Automata, Languages, and Programming
- conference location
- Warsaw, Poland
- conference dates
- 2017-07-10 - 2017-07-14
- external identifiers
-
- scopus:85027264495
- DOI
- 10.4230/LIPIcs.ICALP.2017.91
- language
- English
- LU publication?
- yes
- id
- 1322b88d-f2ea-461c-a46f-225bd8aee829
- date added to LUP
- 2017-07-17 11:48:29
- date last changed
- 2022-03-24 19:51:28
@inproceedings{1322b88d-f2ea-461c-a46f-225bd8aee829, 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.}}, author = {{Björklund, Andreas and Kaski, Petteri and Koutis, Ioannis}}, booktitle = {{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}}, language = {{eng}}, month = {{07}}, pages = {{1--91}}, title = {{Directed Hamiltonicity and Out-Branchings via Generalized Laplacians}}, url = {{http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.91}}, doi = {{10.4230/LIPIcs.ICALP.2017.91}}, year = {{2017}}, }