Exploiting Sparsity for Bipartite Hamiltonicity

Andreas Björklund

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review


We present a Monte Carlo algorithm that detects the presence of a Hamiltonian cycle in an n-vertex undirected bipartite graph of average degree delta >= 3 almost surely and with no false positives, in (2-2^{1-delta})^{n/2}poly(n) time using only polynomial space. With the exception of cubic graphs, this is faster than the best previously known algorithms. Our method is a combination of a variant of Björklund's 2^{n/2}poly(n) time Monte Carlo algorithm for Hamiltonicity detection in bipartite graphs, SICOMP 2014, and a simple fast solution listing algorithm for very sparse CNF-SAT formulas.
Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation (ISAAC 2018)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Print)978-3-95977-094-1
Publication statusPublished - 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018

- Jiaoxi, Yilan, Taiwan
Duration: 2018 Dec 162018 Dec 19


Conference29th International Symposium on Algorithms and Computation, ISAAC 2018

CityJiaoxi, Yilan

Subject classification (UKÄ)

  • Computer Science

Free keywords

  • Hamiltonian cycle
  • bipartite graph


Dive into the research topics of 'Exploiting Sparsity for Bipartite Hamiltonicity'. Together they form a unique fingerprint.

Cite this