## Complexity of equitable partitions

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?
-
 I added an extra problem (now called #2). There is a chance it can be answered by looking at the spectral structure of the graph as such a partition must come from an integer eigenvalue and an eigenvector of that eigenvalue which has only two component values. – Brendan McKay May 14 2012 at 9:13 Nice question, no real idea though I'd guess it is all hard. This might be tough even for the new #2: partition the vertices in two 40/60 (or 50/50) then put on a regular graph structure ( 2 cell equitable) connecting each vertex to about half the others. Knowing that this had been done, how hard is it to recover the partition? Now do (or don't) a small amount of switching like find an edge ab in cell 1 and cd in cell 2 with no cross edges and replace with ac bd. How hard now? – Aaron Meyerowitz May 14 2012 at 12:07 Maybe something eigenvectorish will work for problem #1? If there is a regular partition with at least two cells, then there are two eigenvectors that have repeated entries. Are there graphs without non-trivial equitable partitions that also have this property? – Felix Goldberg May 14 2012 at 14:38 @Felix If there is an eigenvalue of multiplicity greater than 1 then we can take two independent eigenvectors and then arrange in many ways for a linear combination with a repeated entry. – Aaron Meyerowitz May 14 2012 at 16:47 I think that a necessary and sufficient condition for #2 is that the graph has a full orthogonal set of eigenvectors consisting of (1) the eigenvector with constant value that all regular graphs have, (2) a second eigenvector with two different values, defining a partition of two cells, and (3) $n-2$ eigenvectors that sum to 0 on each of the two cells. This generalizes to #1 but I think #2 is already hard enough. – Brendan McKay May 15 2012 at 0:33

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.

-

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.

-
I believe this extends to regular bipartite graphs. Perhaps also to some regular k-partite graphs? Gerhard "Ask Me About System Design" Paseman, 2012.05.13 – Gerhard Paseman May 14 2012 at 2:13
Yes, but many regular graphs do not have any non-trivial equitable partitions. The problem is how quickly can you tell if a particular graph has one or not. – Brendan McKay May 14 2012 at 2:58