pipette
ESEspañol

Breaking the barrier for directed hamiltonicity

Tomohiro Koana, Soh Kumabe

PreprintClaims a big step

In the authors' words

We give a randomized algorithm for Directed Hamiltonian Cycle on -vertex directed graphs that runs in time . For general directed graphs, this is the first improvement in the exponential base over the classical -time algorithms of Bellman and Held--Karp (1962). To obtain this improvement, we first give a -time algorithm for counting Hamiltonian paths modulo two at each total weight when at most distinct weights from enter each vertex. The algorithm combines the Laplacian determinant method of Bj\"orklund, Kaski, and Koutis (ICALP 2017) with a random linearization also used by Arvind and Guruswami (IPEC 2021). To apply the isolation lemma while keeping small, we randomly delete and duplicate arcs, partitioning the incoming copies at each vertex into groups, where . We show that, if the input graph has a Hamiltonian path from to , then with probability at least one can select one group at each vertex other than so that the selected arcs contain an odd number of such paths.

Main resultLimitation the authors admit

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.