License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.15
URN: urn:nbn:de:0030-drops-136601
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13660/
Go to the corresponding LIPIcs Volume Portal

Björklund, Andreas

An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs

pdf-format:
LIPIcs-STACS-2021-15.pdf (0.7 MB)

Abstract

We present a polynomial space Monte Carlo algorithm that given a directed graph on n vertices and average outdegree δ, detects if the graph has a Hamiltonian cycle in 2^{n-Ω(n/δ)} time. This asymptotic scaling of the savings in the running time matches the fastest known exponential space algorithm by Björklund and Williams ICALP 2019. By comparison, the previously best polynomial space algorithm by Kowalik and Majewski IPEC 2020 guarantees a 2^{n-Ω(n/(2^δ))} time bound.
Our algorithm combines for the first time the idea of obtaining a fingerprint of the presence of a Hamiltonian cycle through an inclusion-exclusion summation over the Laplacian of the graph from Björklund, Kaski, and Koutis ICALP 2017, with the idea of sieving for the non-zero terms in an inclusion-exclusion summation by listing solutions to systems of linear equations over ℤ₂ from Björklund and Husfeldt FOCS 2013.

BibTeX - Entry

@InProceedings{bjorklund:LIPIcs.STACS.2021.15,
  author =	{Bj\"{o}rklund, Andreas},
  title =	{{An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13660},
  URN =		{urn:nbn:de:0030-drops-136601},
  doi =		{10.4230/LIPIcs.STACS.2021.15},
  annote =	{Keywords: Hamiltonian cycle, directed graph, worst case analysis algorithm}
}

Keywords: Hamiltonian cycle, directed graph, worst case analysis algorithm
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI