Algorithm for partitioning graph vertices into sets of indistinguishable vertices in unlabeled graphs

Question

Given a graph G=(V,E) I'd like to group its vertices into sets, so that indistinguishable vertices go in the same set and vertices that are structurally different go into different sets. Consider the following example:

With this example I'd like to get to exactly these four sets, however I don't know how to get there. If I use the adjacency matrix of the graph the four vertices in set 1 and 2 all end up in a different set. And if I only look at the degrees, vertices from set 1 and 4 end up in the same set. I guess that if I get the same result from my two methods the result is correct, however that only works for a small subset of graphs and I'm looking for a general approach that works for all graphs (or at least connected graphs).

In practice I could use the naive approach of just looking at all possible labelings of my graph and see if I get the same adjacency matrix for a different labeling and based on that infer equivalent vertices. My graphs aren't even that big, approx. 10-12 nodes, but as I have to do this for a large number of graphs I hope there is a more efficient approach.

Answer 1

There is no straightforward way to do this that's better than brute force, because this is as hard as graph isomorphism. (If you want to know whether $G \cong H$ and have this partitioning algorithm, you can run it on the disjoint union of $G$ and $H$, and check if any vertex in $G$ is in the same set as any vertex in $H$.)

For very small graphs, it might be easiest to use brute force. For larger graphs, you probably want to use existing software rather than write your own algorithm. In particular...

---

...this can be done with nauty. The labeling you are looking for is the array of the orbits of the automorphism group. The manual goes into the details of how to find it, but here is a summary:

• To do this for one graph at a time, you could use the dreadnaut interface. You'll need the n=# g command to enter the graph, the x command to run nauty, and the O command to get the orbits.
• In a C program, you can call densenauty with a whole bunch of parameters, one of which (int* orbits) will contain the orbits after nauty is called.

In the C program, and I believe in dreadnaut as well, the $k$ orbits will not be labeled $1$ through $k$; rather, each vertex in an orbit will be labeled with the number of the first vertex in that orbit.

---

... in Mathematica, you can do this with GroupOrbits[GraphAutomorphismGroup[graph]]. This will not be as efficient as nauty or other graph isomorphism software for large graphs.

---

... igraph is a graph algorithm library with interfaces in several languages. I've only ever used it in Mathematica, where you could improve on the solution above (for large graphs) with GroupOrbits[IGBlissAutomorphismGroup[graph]] after loading IGraph. But I assume you can do the equivalent in R, Python, and C++ just as easily.