case of (ii) identifies the partition $U_1,U_2$ of $U$. We call this Algorithm 3.

\[th:alg6\] For each fixed choice of parameters $1/n_0 \ll \rho \ll \nu \ll \rho'\ll \tau \ll \alpha < 1$ there exists a polynomial-time algorithm that does the following. Given a $D$-regular $n$-vertex graph $G=(V,E)$ and $U \subseteq V$ as input, where $D \geq \alpha n$, $n \geq n_0$, and $G[U]$ is a $\rho$-component, the algorithm determines that either

1.  $G[U]$ is a robust $(\nu,\tau)$-expander, or

2.  $G[U]$ is a bipartite robust $(\nu,\tau)$-expander, or

3.  $U$ has a partition $U_1$, $U_2$ such that $G[U_1]$, $G[U_2]$ are $\rho'$-components,

and in the case of (ii) and (iii) identifies the corresponding partition. We call this Algorithm 4.

In each of the four lemmas above, the algorithm distinguishes between various cases. It may be that more than one of these cases hold for the given input graph; if so then the algorithm will output any one case that holds for the given graph.

The running time of each of the algorithms is $O(n^3)$, where $n$ is the number of vertices of the input graph. The running time does not depend at all on the fixed parameters (not even as hidden constants 