2026-07-22T10:47:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9951 2024-03-06T10:45:11Z ddc:004 open_access

Exploiting Sparsity for Bipartite Hamiltonicity Björklund, Andreas Hamiltonian cycle bipartite graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Björklund 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.3 urn:nbn:de:0030-drops-99510 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode