and Osthus [@Robb2] about algorithms to check whether a graph is a robust expander in polynomial time; this result and its background are presented in Section \[sec:digression\] after robust expansion has been formally defined.

Once we have the algorithm for constructing the robust expander partition, we will also require a result of Letzter and Gruslys [@CyclePartitions] for finding certain structures between the parts in this partition. Combining all of this with some further algorithmic ingredients will yield the desired algorithm.

Below we give a more detailed account of our algorithm as well as the proof of the hardness results (Proposition \[pr:hard\]) mentioned above. In Section \[sec:notation\] we give some general notation and we formally define robust expansion, as well stating some of the results from spectral graph theory that we will need in later sections. In Section \[sec:robustparts\], we give the algorithm for finding the robust expander partition mentioned above, and Section \[sec:findingcycles\] is about utilizing the structure of a robust partition to find a long cycle. This is where the proof of Theorem \[thm:main\] is given.

Proof outline
-------------

We now go into more detail about our algorithm. The first step of the algorithm, given in Section \[sec:robustparts\], is 