A distributed algorithm for finding Hamiltonian cycles in random graphs in O(log⁡n) time

Abstract

It is known for some time that a random graph G(n,p) contains w.h.p. a Hamiltonian cycle if p is larger than the critical value pcrit=(log⁡n+log⁡log⁡n+ωn)/n. The determination of a concrete Hamiltonian cycle for G(n,p) is a nontrivial task, even when p is much larger than pcrit. In this paper we consider random graphs G(n,p) with p in Ω˜(1/n), where Ω˜ hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm AHC that finds w.h.p. a Hamiltonian cycle in O(log⁡n) rounds. The algorithm works in the synchronous model and uses messages of size O(log⁡n) and O(log⁡n) memory per node.