We follow this argument closely, except that the existence of $A,B$ is not enough for us: we need a polynomial-time algorithm to find $A$ and $B$. We make use of spectral algorithms to achieve this.

In the second step, given in Section \[sec:findingcycles\], we make use of the robust partition to decide whether a very long cycle exists. Using further results from [@kuhn2014robust], it turns out that a very long cycle exists if and only if a certain type of structure exists between the parts of our robust partition. With the help of a result from [@CyclePartitions], we give a fast algorithm to determine whether such a structure is present in our graph and to find it if it is. We will give a more detailed sketch of this at the start of Section \[sec:findingcycles\].

We end this subsection by proving the simple hardness results mentioned earlier in the introduction.

\[pr:hard\] For each fixed integer $C \geq 0$ and each real $\alpha \in (0, 1/2)$ the following holds.

-   The problem of deciding whether a regular $n$-vertex graph has a cycle of length at least $n - C$ is NP-complete.

-   The problem of deciding whether an $n$-vertex graph of 