Directed Hamiltonicity and OutBranchings via Generalized Laplacians
(2017) 44th International Colloquium on Automata, Languages, and Programming p.191 Abstract
 We are motivated by a tantalizing open question in exact algorithms: can we detect whether an nvertex 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^((1lambda)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^(nalpha(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 nvertex 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^((1lambda)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^(nalpha(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 exponentialspace 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 Laplacianlike matrices, inspired by the MatrixTree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the MatrixTree Theorem to derive simple algebraic algorithms for detecting outbranchings. Specifically, we give an O^*(2^k)time randomized algorithm for detecting outbranchings 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 kLeaf problem, based on a nonstandard monomial detection problem. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1322b88df2ea461ca46f225bd8aee829
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri and Koutis, Ioannis
 organization
 publishing date
 20170710
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
 pages
 14 pages
 conference name
 44th International Colloquium on Automata, Languages, and Programming
 conference location
 Warsaw, Poland
 conference dates
 20170710  20170714
 external identifiers

 scopus:85027264495
 DOI
 10.4230/LIPIcs.ICALP.2017.91
 language
 English
 LU publication?
 yes
 id
 1322b88df2ea461ca46f225bd8aee829
 date added to LUP
 20170717 11:48:29
 date last changed
 20190423 04:11:21
@inproceedings{1322b88df2ea461ca46f225bd8aee829, abstract = {We are motivated by a tantalizing open question in exact algorithms: can we detect whether an nvertex 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^((1lambda)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^(nalpha(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 exponentialspace 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 Laplacianlike matrices, inspired by the MatrixTree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the MatrixTree Theorem to derive simple algebraic algorithms for detecting outbranchings. Specifically, we give an O^*(2^k)time randomized algorithm for detecting outbranchings 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 kLeaf problem, based on a nonstandard monomial detection problem. }, author = {Björklund, Andreas and Kaski, Petteri and Koutis, Ioannis}, language = {eng}, location = {Warsaw, Poland}, month = {07}, pages = {191}, title = {Directed Hamiltonicity and OutBranchings via Generalized Laplacians}, url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.91}, year = {2017}, }