# 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 '12 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 '12 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 '12 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 '12 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 '12 at 0:33

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.

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.

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).

• Thanks, but I don't see how to make that work. What equitable partition condition is equivalent to having an automorphism exchanging the sides? – Brendan McKay Dec 15 '15 at 13:32
• You are right. However, here is a suggestion which may not satisfy your requirement. Order 2 fixed-point free automorphism gives rise to undirected cells of two elements. If you drop the order 2 condition you get directed cells. – Mohammad Al-Turkistany Dec 15 '15 at 14:29 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 '12 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 '12 at 2:58