I'm analyzing data in a social network, represented as a graph. We have a guarantee that there exists a partition (V1, V2) of equal size (plus or minus 1), where either each vertex of V1 is connected to every vertex of V2, or connected to no vertex of V2, or no vertex of V1 is connected to any vertex of V2. Furthermore, this property is recursive, i.e. each of the two subgraphs generated by this partition have the property as well.
So far I've used a naive, inefficient "guess-and-check" approach which works in our toy examples, but this will not work for larger data sets. I imagine there is a recursive approach that will work better. Any ideas?