Complexity of equitable partitions

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

Here is a partial answer to your fourth question.

The Fractional Graph Isomorphism problem (see the relevant paper and book) is related to the problem of computing equitable partitions of a graph. The Fractional Graph is no harder than the Graph Isomorphism problem so it seems likely that many problems on equitable partitions will be no harder than the Graph Isomorphism problem.

Consider the Graph Isomorphism problem as the problem of determining whether there is a permutation matrix $P$ such that $AP = PB$, where $A$ and $B$ are the adjacency matrices of the two graphs. This is really the problem of determining the feasibility of an integer linear program (where the entries of $P$ are the unknown variables).

The Fractional Graph Isomorphism problem is the relaxation that allows $P$ to be a doubly stochastic matrix instead of a permutation matrix. Now this problem can be posed as a linear program instead of an integer linear program, so it can be solved in polynomial time. (It is unknown whether Graph Isomorphism can be solved in polynomial time, and more generally, integer linear programming cannot be solved in polynomial time unless $\mathsf{P} = \mathsf{NP}$.)

According to the references linked above, the Fractional Graph Isomorphism is equivalent to the problem of determining whether two graphs have a common coarsest equitable partition, or simply any common equitable partition.

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.

Answer 3

For question 4, It is NP-complete to decide whether a bipartite graph $G(V_1 \cup V_2, E)$ has an automorphism of order 2 which interchange the two color classes. If we drop the order 2 requirement then the problem becomes equivalent to Graph Isomorphism problem. The correspondence between order 2 fixed-point free automorphisms and equitable partitions should help you to transfer the last result to equitable partitions (note that the requirement of interchanging the two color classes forces the automorphism to be fixed-point free).

Answer 4

    
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.