On a simple randomized algorithm for finding long cycles in sparse graphs

We analyze the performance of a simple randomized algorithm for finding long cycles and 2-factors in directed Hamiltonian graphs of out-degree at most two and in undirected Hamiltonian graphs of de-gree at most three. For the directed case, the algorithm finds a 2-factor in O(n²) expected time. The analysis of our algorithm is based on random walks on a line and interestingly resembles the analysis of a randomized algorithm for the 2-SAT problem given by Papadimitriou [15]. For the undirected case, the algorithm finds a 2-factor in O(n³) expected time. We also analyze random versions of these graphs and show that cycles of length Ω(n / log n) can be found with high probability in polynomial time. This partially answers an open question of Broder et al. [4] on finding hidden Hamiltonian cycles in sparse random graphs and improves on a result of Karger et al. [13]