Finding a long directed cycle
Harold N. Gabow, Shuxin Nie · ACM Transactions on Algorithms · 2008
Consider a digraph with n vertices. For any fixed value k , we present linear- and almost-linear-time algorithms to find a cycle of length ≥ k , if one exists. We also find a cycle that has length ≥ log n /log log n in polynomial time, if one exists. Under an appropriate complexity assumption it is known to be impossible to improve this guarantee by more than a log log n factor. Our approach is based on depth-first search.