  In 1959, Erd\H{o}s and Gallai proved that every graph G with average vertex
degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an
algorithm that for k\geq 0 in time 2^{O(k)} n^{O(1)} decides whether a
2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This
resolves an open problem explicitly mentioned in several papers. The main
ingredients of our algorithm are new graph-theoretical results interesting on
their own.
