Breaking the $2^n$ barrier for directed hamiltonicity

We give a randomized algorithm for Directed Hamiltonian Cycle on $n$-vertex directed graphs that runs in time $O^{\ast }((375\mathrm{/}196{)}^n)=O^{\ast }({1.9133}^n)$. For general directed graphs, this is the first improvement in the exponential base over the classical $O^{\ast }(2^n)$-time algorithms of Bellman and Held–Karp (1962). To obtain this improvement, we first give a $(2-2^{-d}{)}^n\text{poly}(n,W)$-time algorithm for counting Hamiltonian paths modulo two at each total weight when at most $d$ distinct weights from $\{1,\dots ,W\}$ enter each vertex. The algorithm combines the Laplacian determinant method of Björklund, Kaski, and Koutis (ICALP 2017) with a random linearization also used by Arvind and Guruswami (IPEC 2021). To apply the isolation lemma while keeping $d$ small, we randomly delete and duplicate arcs, partitioning the incoming copies at each vertex into $d$ groups, where $d\ge 2$. We show that, if the input graph has a Hamiltonian path from $s$ to $t$, then with probability at least ${(1-\frac{1}{1+(2^d-1{)}^2})}^{n-1}$ one can select one group at each vertex other than $s$ so that the selected arcs contain an odd number of such paths.