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:
- 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?
- What is the complexity of: Given a regular graph, does it have an equitable partition with exactly two cells?
- 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?
- Is there any problem on equitable partitions with complexity equal to graph isomorphism?
Best Answer
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.