Directed hamiltonicity and out-branchings via generalized laplacians
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2017-07-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-14
Series
44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Leibniz International Proceedings in Informatics, Volume 80
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 2n? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0 < λ < 1 and prime p we can count the Hamiltonian cycles modulo p[(1-λ) n/3p] in expected time less than cn for a constant c < 2 that depends only on p and λ. Such an algorithm was previously known only for the case of counting modulo two [Björklund and Husfeldt, FOCS 2013]. 2. We show that we can detect a Hamiltonian cycle in O∗(3n-α(G)) time and polynomial space, where α(G) is the size of the maximum independent set in G. In particular, this yields an O∗(3n/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κ)-time randomized algorithm for detecting out-branchings with at least k internal vertices, improving upon the algorithms of [Zehavi, ESA 2015] and [Björklund et al., ICALP 2015]. We also present an algebraic algorithm for the directed k-Leaf problem, based on a non-standard monomial detection problem.Description
Keywords
Counting, Directed Hamiltonicity, Graph Laplacian, Independent set, Kinternal out-branching
Other note
Citation
Björklund, A, Kaski, P & Koutis, I 2017, Directed hamiltonicity and out-branchings via generalized laplacians . in 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 ., 91, Leibniz International Proceedings in Informatics, vol. 80, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-14, International Colloquium on Automata, Languages and Programming, Warsaw, Poland, 10/07/2017 . https://doi.org/10.4230/LIPIcs.ICALP.2017.91