  We consider the problem of finding a cycle in a sparse directed graph $G$
that is promised to be far from acyclic, meaning that the smallest feedback arc
set in $G$ is large. We prove an information-theoretic lower bound, showing
that for $N$-vertex graphs with constant outdegree any algorithm for this
problem must make $\tilde{\Omega}(N^{5/9})$ queries to an adjacency list
representation of $G$. In the language of property testing, our result is an
$\tilde{\Omega}(N^{5/9})$ lower bound on the query complexity of one-sided
algorithms for testing whether sparse digraphs with constant outdegree are far
from acyclic. This is the first improvement on the $\Omega(\sqrt{N})$ lower
bound, implicit in Bender and Ron, which follows from a simple birthday paradox
argument.
