jats:titleAbstract</jats:title> jats:pWe study the problem of assortative and disassortative partitions on random jats:italicd</jats:italic>-regular graphs. Nodes in the graph are partitioned into two non-empty groups. In the assortative partition every node requires at least jats:italicH</jats:italic> of their neighbors to be in their own group. In the disassortative partition they require less than jats:italicH</jats:italic> neighbors to be in their own group. Using the cavity method based on analysis of the belief propagation algorithm we establish for which combinations of parameters (jats:italicd</jats:italic>, jats:italicH</jats:italic>) these partitions exist with high probability and for which they do not. For jats:inline-formula jats:tex-math \lceil \frac{d}{2}\rceil $?></jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> mml:miH</mml:mi> mml:mo></mml:mo> mml:mrow mml:mo⌈</mml:mo> mml:mrow mml:mfrac mml:mrow mml:mid</mml:mi> </mml:mrow> mml:mrow mml:mn2</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> mml:mo⌉</mml:mo> </mml:mrow> </mml:math> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="aac8b46ieqn1.gif" xlink:type="simple" /> </jats:inline-formula> we establish that the structure of solutions to the assortative partition problems corresponds to the so-called frozen-one-step replica symmetry breaking. This entails a conjecture of algorithmic hardness of finding these partitions efficiently. For jats:inline-formula jats:tex-math</jats:tex-math> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> mml:miH</mml:mi> mml:mo⩽</mml:mo> mml:mrow mml:mo⌈</mml:mo> mml:mrow mml:mfrac mml:mrow mml:mid</mml:mi> </mml:mrow> mml:mrow mml:mn2</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> mml:mo⌉</mml:mo> </mml:mrow> </mml:math> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="aac8b46ieqn2.gif" xlink:type="simple" /> </jats:inline-formula> we argue that the assortative partition problem is algorithmically easy on average for all jats:italicd</jats:italic>. Further we provide arguments about asymptotic equivalence between the assortative partition problem and the disassortative one, going through a close relation to the problem of single-spin-flip-stable states in spin glasses. In the context of spin glasses, our results on algorithmic hardness imply a conjecture that gapped single spin flip stable states are hard to find which may be a universal reason behind the observation that physical dynamics in glassy systems display convergence to marginal stability.</jats:p>