License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.91
URN: urn:nbn:de:0030-drops-74208
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7420/
Björklund, Andreas ;
Kaski, Petteri ;
Koutis, Ioannis
Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
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.
BibTeX - Entry
@InProceedings{bjrklund_et_al:LIPIcs:2017:7420,
author = {Andreas Bj{\"o}rklund and Petteri Kaski and Ioannis Koutis},
title = {{Directed Hamiltonicity and Out-Branchings via Generalized Laplacians}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {91:1--91:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7420},
URN = {urn:nbn:de:0030-drops-74208},
doi = {10.4230/LIPIcs.ICALP.2017.91},
annote = {Keywords: counting, directed Hamiltonicity, graph Laplacian, independent set, k-internal out-branching}
}
|
Keywords: |
|
counting, directed Hamiltonicity, graph Laplacian, independent set, k-internal out-branching |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
