Question

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any cell $C$, it holds that $v,w$ have the same number of neighbours in $C$. The trivial partition (with only one vertex per cell) is always equitable.

Given any partition $\pi$, there is a unique coarsest equitable partition $\bar\pi$ finer than $\pi$. (The concepts finer and coarser include equality). This is a very old result, as also are polynomial-time algorithms for computing $\bar\pi$ from $\pi$.

Another fact is that it is NP-complete to determine if a graph has an equitable partition with every cell of size 2. (This follows from Lubiw, SIAM J Comput 10, 1981, 11–21 on noting that such a partition corresponds to a fixed-point-free automorphism of order 2.)

My question is: what else? Are any other complexity results known? In particular:

1. What is the complexity of: Given a regular graph, does it have any non-trivial equitable partition other than the partition with just one cell?
2. What is the complexity of: Given a regular graph, does it have an equitable partition with exactly two cells?
3. What is the complexity of: Given a graph and two vertices $v,w$, is there a non-trivial equitable partition which has $v,w$ in different cells?
4. Is there any problem on equitable partitions with complexity equal to graph isomorphism?

Answer 1

    
Concerning Question 1, it seems that partitioning a hypercube into two diagonally crossing sets is an equipartition: in the two examples shown, each blue vertex has two neighbors in the purple set, and vice versa. This continues to hold for $d$-dimensional hypercubes, providing an example of a $d$-regular graph with a 2-equipartition.

Answer 2

More a comment than an answer. I have (as suggested) asked a related question which is essentially about the complexity of determining if a certain eigenspace has a member with two distinct entries.

Related to this question, here is an astonishingly vague sketch of a possible type of approach for an attempted construction of a potentially difficult example for question 2: Start with a connected bipartite graph $H$ which has $2m$ vertices $v_1 \cdots v_{2m}$ all of degree $d$ (so the two halves each have $m$ vertices) but is otherwise fairly irregular. Also generate $2m$ graphs $G_1 \cdots G_{2m}$ each with $n$ vertices, regular of degree $d^*$ and all having $0$ as an eigenvalue of reasonably high multiplicity but without any very simple eigenvectors. Now make them into a big graph $\mathcal{G}$ with $2mn$ vertices by putting in all $n^2$ edges connecting $G_i$ and $G_j$ whenever $v_iv_j$ is an edge of $H.$ There will be an enormous number of fairly complicated eigenvectors of $\mathcal{G}$ obtained by picking an arbitrary eigenvector of $0$ for each of the $G_i.$ There will also be an eigenvector which is $1$ on half the vertices and $-1$ on the other half (respecting the bipartition of $H$.) Now if the graph is just presented as a huge adjacency matrix with vertices in a very scrambled order then it will be clear that $0$ is an eignevalue of high multiplicity and our favorite program will present us a basis for the corresponding eigenspace, but it may not be obvious how to find that special eigenvector.

Left unspecified is how to pick good values for $m,n,d,d^*$ Perhaps there is a simple flaw in this description, maybe too many easy to find $0,1,-1$ eigenvectors. In that case I say that that was only a sketch. In some other way build in an equitable (two cell) partition overlaid with lots of noise.