Directed hamiltonicity and out-branchings via generalized laplacians

Andreas Björklund, Petteri Kaski, Ioannis Koutis

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)
39 Downloads (Pure)

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.

Original languageEnglish
Title of host publication44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-14
ISBN (Electronic)9783959770415
DOIs
Publication statusPublished - 1 Jul 2017
MoE publication typeA4 Article in a conference publication
EventInternational Colloquium on Automata, Languages, and Programming - Warsaw, Poland
Duration: 10 Jul 201714 Jul 2017
Conference number: 44

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume80
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages, and Programming
Abbreviated titleICALP
CountryPoland
CityWarsaw
Period10/07/201714/07/2017

Keywords

  • Counting
  • Directed Hamiltonicity
  • Graph Laplacian
  • Independent set
  • Kinternal out-branching

Fingerprint Dive into the research topics of 'Directed hamiltonicity and out-branchings via generalized laplacians'. Together they form a unique fingerprint.

Cite this