Finding Hamilton cycles in robustly expanding digraphs

Abstract

We provide an NC algorithm for finding Hamilton cycles in directed graphs with a certain robust expansion property. This property captures several known criteria for the existence of Hamilton cycles in terms of the degree sequence and thus we provide algorithmic proofs of (i) an `oriented' analogue of Dirac's theorem and (ii) an approximate version (for directed graphs) of Chvátal's theorem. Moreover, our main result is used as a tool in a recent paper by Kühn and Osthus, which shows that regular directed graphs of linear degree satisfying the above robust expansion property have a Hamilton decomposition, which in turn has applications to TSP tour domination.