# How to find a good individualising set in graph isomorphism

The procedure called individualization breaks symmetry arbitrarily. It chooses some nodes in the graph, arbitrarily, to give their own unique names.

Suppose there exists a set $S \subset V$, such that after individualising this set and running plane WL (Weisfeiler-Lehman) algorithm each vertex gets a unique label (i.e. discretised ). There may be other subsets of $V$ of same size as $S$, whose individualisation (after running WL procedure) does not assign unique label to each vertex of input graph.

I am not individualising $k$ vertices simultaneously, but individualising one and then running the WL procedure.

Is there any way to minimise the individualising set size? if it is given that after individualising $l$ many vertices are sufficient.

Question : After individualising one vertice of input graph and then running the WL, I will have say some equitable partitions of vertex set of input graph $G$. How to pick second vertex for individualisation process? To me it appears I should choose a vertex who has say almost same number of neighbours and non-neighbours. I have tried some other parameters like degree etc to pick second vertex, but don't seems working. The best choice seems to me the vertex, which belong to same orbit as first vertex.

Please note that I don't want to try all possible choices of $S$ and looking from theoretical point of view completely.

EDIT: If input graph is regular then choice of first vertex is not important. I mean to say there is always going to be an individualising set (minimum size) which contain this first vertex. As input graph is regular, the number of neighbours and non-neighbours set size will be same for every choice of first vertex.

• I am guessing that one cannot find the exact minimum-size set without trying all possibilities. It sounds like you are looking for an algorithm to run in practice (rather than worst-case guarantees). In that case, you might try looking at the color-distance partition from each vertex (from a given v, how many vertices have color c and distance d from v?) and choose the vertex for which its color-distance partition has the most parts. – Joshua Grochow Oct 2 '17 at 19:50
• Maybe, you can use the graph signature, if A is a characteristic matrix of the graph, then P(X)=det(A-XId) is a signature of the graph. – Dattier Oct 3 '17 at 10:28

It depends on the type of graph. Whatever algorithm you choose there are probably graphs that it works badly on. Similarly, given a vertex choice method, there are graphs it is bad for. Here are two examples:

The first is one where it is unwise to pick a vertex adjacent to half the others. Let $G$ be a strongly regular graph with $n$ vertices of degree $d$ where $d \leq \frac{n}{2}.$ Then make a new bipartite graph also regular of degree $d$ but with twice as many vertices by replacing each vertex $x$ by a pair $x_1,x_2$ and each edge $(x,y)$ by the $2$ edges $(x_1,y_2)$ and $(y_1,x_2)$ Finally, add two new vertices $X_1$ and $X_2$ with $X_1$ adjacent to all the $u_2$ (and also $X_2$) and $X_2$ adjacent to all the $u_1$ (and also $X_1$.) These two new vertices are the only ones adjacent to half the vertices (the rest are adjacent to under a quarter of the vertices.) But picking an $X_i$ as a named vertex at any stage is of little to no use.

To give an example where your second idea does not do well I need to know what you mean by "in the same orbit." Are you saying that the graph (before any vertices get names) has an automorphism group with orbits and the first two points chosen come (one at a time) from the same orbit? I don't like this construction as much as the other one, but replace every vertex $x$ by a $K_m$ with vertices $x_1,x_2,\cdots,x_m.$ Then replace every edge $(x,y)$ with the $m$ edges $(x_i,y_i).$ If your first chosen vertex is, say, $u_1$ then certainly $u_2$ is in the same orbit but picking it next is not very helpful. I suppose that a distinguishing set must utilize at least $m-1$ of the labels. Now it might be that some $v_2$ is a good thing to pick next but your rule would make picking $v_1$ equally attractive, which it shouldn't be. Since I don't know for sure what your suggestion is, I'll stop there. Except to say that $m$ need not be too large. I do like the idea that there is no $m$-clique in the starting graph. Then it is obvious if an edge is of the type $(x_i,x_j)$ or of type $(x_i,y_i).$

• Thanks for the answer. Picking $X_i$'s as a named vertices are of use. Because picking say $X_1$, I will be able to differentiate between vertices of one partition from the another. individualising $X_1$, will change the labelings of the vertices in a partition in which $X_1$ has neighbours. Suppose I am not naming any vertex then there are only two types of labels are there in the graph you have mentioned. – fddwd Oct 3 '17 at 8:41
• Before you label anything there are $2$ types. If you pick an $X_i$ first you get $4$ types. If you pick a $u_1$ you have at least $6$ types and maybe more. The question was also about the second choice. Whatever the first choice is, picking an $X_i$ second gives no new information at all. – Aaron Meyerowitz Oct 3 '17 at 9:32
• Yes definitely, I thought in the first paragraph you were saying about any stage in the process. – fddwd Oct 3 '17 at 9:35
• After applying WL algorithm we will get partitions, now each such partition is a union of orbits. Any one partition may contain two or more orbits. – fddwd Oct 3 '17 at 12:39
• Yes, but once you individualize a vertex it becomes the only member of its cell in the partition . It is in an orbit of size 1. – Aaron Meyerowitz Oct 3 '17 at 13:21