Directed hamiltonian cycle algorithm runs faster than two to the n
Breaking the $2^n$ barrier for directed hamiltonicity
Data Structures and Algorithms
Summary
The problem is finding a special type of route in a network of one-way streets, visiting every intersection exactly once, which is very hard to do quickly. The authors present a new randomized method that solves this problem faster than all previous known methods for general networks. They use advanced techniques involving counting certain paths in clever ways and handling random choices to improve speed. This is the first time the running time has been significantly reduced below the old standard of checking all possibilities.
What this means in practice
- •For network schedulers: Use the improved algorithm to find efficient routes that visit all nodes in networks with directed links faster than before.
- •For logistics planners: Speed up planning of routes that must visit all locations exactly once in systems modeled by directed graphs, enabling larger problem instances.
A theory result. No direct application yet.
Authors
Tomohiro Koana, Soh Kumabe
Abstract
We give a randomized algorithm for Directed Hamiltonian Cycle on $n$-vertex directed graphs that runs in time $O^*((375/196)^n)=O^*(1.9133^n)$. For general directed graphs, this is the first improvement in the exponential base over the classical $O^*(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,\ldots,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\ge2$. We show that, if the input graph has a Hamiltonian path from $s$ to $t$, then with probability at least $\left(1-\frac{1}{1+(2^d-1)^2}\right)^{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.