$n$ vertices where $D\geq \alpha n$. Let $\mathcal{V}$ be a robust partition of $G$ with parameters $\rho,\nu,\tau,k ,\ell$. Then $\mathcal{V}$ is a weak robust subpartition of $G$ with parameters $\rho,\nu,\tau,\eta,k,\ell$.

Robust partitions {#sec:robustparts}
=================

Statements of algorithms
------------------------

In this section we present an algorithm (Theorem \[th:decompose\]) that we use to find robust partitions (see previous section for the definition) of regular graphs. As mentioned earlier, the main algorithm and its analysis are obtained by combining the robust expander decomposition of regular graphs from [@kuhn2014robust] together with spectral algorithms for graph partitioning from [@trevisan2012max; @trevisanLectureNotes].

We begin by presenting four algorithms in the following lemmas that will eventually be used together to obtain the main algorithm. The proofs appear in the following subsection.

\[th:alg1\] 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 of $G$ that is not $\rho'$-close to bipartite, the algorithm determines that either

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

2.  $U$ has 