# Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

'In discussing Johnson graphs, Babai said they were a source of “unspeakable misery” for people who want to solve GI quickly. At the same time, it is a “curse and a blessing,” as once you’ve found a Johnson graph embedded in your problem you can recurse to much smaller instances. This routine to find one of these three things is called the “split-or-Johnson” routine.'

(1) Are Isospectral Johnson graphs the hardest case to find Isomorphism?

(2) In general what makes a graph class hard to tame (Isomorphism difficult for this class)?

(3) Supposing we know that two graphs are isomorphic. Suppose our goal is to find say isomorphism between any of $\alpha\log N$ vertices of the $N$ vertices for some $\alpha >0$. How difficult is to accomplish this? If you pick a random choice of $\alpha\log N$ on an average how many spurious matches could we land up with as candidate isomorphisms on the other graph based on these fixed $\alpha\log N$ vertices?

• If the isomorphic graphs are sparse (say trees or forests) with only the trivial automorphism then a random choice $\alpha\log N$ vertices is highly likely to be disjoint leading to many spurious matches. Even a cycle (or the complement) would be problematic in this regard. – Aaron Meyerowitz Jan 4 '16 at 7:20
• @AaronMeyerowitz But do Johnson graphs have trivial automorphism? May be Johnson graphs do not have such large spurious matches? – user76479 Jan 4 '16 at 7:26
• No, Johnson Graphs have many automorphisms. I thought you were asking about graphs in general. Also, when you say an automorphisms on a random small vertex set, do you mean preserving incidence and non/incidence or do you mean preserving distance in the big graphs? – Aaron Meyerowitz Jan 4 '16 at 9:20
• @AaronMeyerowitz You have graphs G1 and G2. Pick a random log N vertex set in G1 try to find some correspondence with G2 and proceed with iteration on guarantee that all partial matches are compatible. Technically if all goes well it is capable of giving a O(n^\log n) complexity algorithm if there are not that many spurious hits. – user76479 Jan 4 '16 at 11:29
• i have a really good algorithm for graph isomorphic. link for a polynomial time algorithm for graph isomorphic testing and mapping – Ahmad Jul 26 '16 at 0:48

Johnson graphs do not cause difficulty to existing programs. Actually they are rather easy; nauty can handle them up to tens of millions of vertices, and so can other programs such as Traces and Bliss.

The difficulty that Babai refers to is more theoretical. The Johnson graph $J(v,t)$, which has $n=\binom vt$ vertices, has the property that $\Theta(n^{1/t})$ vertices need to be fixed in order for partition refinement to produce a partition with all cells at most $cn$ in size ($c<1$), nor does the group have a nice recursive structure like a wreath product. Babai says that a major part of his breakthrough was to realise that only the Johnson graphs (and closely related graphs) have these undesirable properties. With that knowledge, special processing takes care of them. Previously it could have been that some other families of graphs exist with similar properties.

I think this description is reasonably close. I recently listened to Babai speaking on his algorithm for 5 hours but some parts remain unclear to me.

Btw, the automorphism group of $J(v,t)$ for $t\lt v/2$ is $S_v$ acting on $t$-sets. Programs find them easy because of this rich group.

About the "supplementary problem", fixing $O(\log n)$ vertices helps very little. It is necessary to match $\Theta(n^{1/t})$ vertices in each graph before elementary methods will provide much further information about isomorphisms. It's hard to define "elementary methods", but they include all the obvious things like classifying vertices according to their adjacencies with the fixed vertices and more generally fixed-dimensional Weissfeiler-Lehman refinement.

Babai's statement that you quote is easy to misunderstand. It isn't the Johnson graphs themselves that were a scourge to theorists. It's more that the Johnson graphs showed that certain difficult structural properties (mentioned above) are possible and nobody knew a general method for handling these properties. Once Babai showed that only the Johnson graphs caused that structure, the difficultly vanished.

• what about the supplementary problem I posted regarding local identification of isomorphism between log N vertices on the most challenging graphs? – user76479 Jan 4 '16 at 8:17
• For $t \lt v/2$ it is $S_v$ but for $t=v/2 \gt 1$ it is twice as large due to the map sending each $t$-set to its complement. – Aaron Meyerowitz Jan 4 '16 at 22:21
• @Aaron: Yes, that's a typo I will fix immediately. – Brendan McKay Jan 5 '16 at 2:07
• @Arul: If you fix $m$ vertices, it is like fixing $m$ $t$-subsets of a $v$-set. This impacts at most $mt$ elements of the $v$-set, so at least $v-mt$ elements are not impacted and are still equivalent to each other. This means in the graph that there are at least $\binom{v-mt}{t}$ equivalent vertices. For $t$ constant and $m=o(v/t^2)$ this means that most of the vertices of the graph are still not distinguished from each other. (continued) – Brendan McKay Jan 5 '16 at 9:53
• @Arul: Continuing: Babai showed that for other graphs, if you fix only $(log n)^{O(1)}$ vertices one of two things happen. Either the equivalence classes of vertices are all small (less than $cn$ for $c<1$), or there is a wreath-product-like decomposition into smaller graphs. (Something like that, anyway ;)). – Brendan McKay Jan 5 '16 at 9:55