On testing Hamiltonicity of graphs.

Let us fix a function f ( n ) = o ( n ln n ) and real numbers 0 ≤ α < β ≤ 1 . We present a polynomial time algorithm which, given a directed graph G with n vertices, decides either that one can add at most β n new edges to G so that G acquires a Hamiltonian circuit or that one cannot add α n or fewer new edges to G so that G acquires at least e − f ( n ) n ! Hamiltonian circuits, or both. [ABSTRACT FROM AUTHOR]