A probabilistic polynomial algorithm for solving a directed Hamiltonian Path problem

Abstract: "In this paper we present a graph-theoretic polynomial algorithm which has positive probability of finding a Hamiltonian Path in a given graph, if there is one; if the algorithm fails, it can be rerun with a randomly chosen starting solution, and there is again a positive probability it will find an answer. If there is no Hamiltonian Path, the algorithm will always terminate with failure. Some basic theoretical results concerning spanning arborescences of a graph are given. The concept of a ramification index is defined and it is shown that ramification index of a Hamiltonian Path is zero. The algorithm starts with finding any arborescence and by suitable pivots it endeavors to reduce the ramification index to zero. Probabilistic properties of the algorithm are discussed. Computational experience with graphs up to 30,000 nodes is included."