Solving the Hamilton cycle problem fast on average
We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥
100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and
Krivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n
−1/2 respectively.
2022-October
919-930
919-930
Institute of Electrical and Electronics Engineers