3
$\begingroup$

Looking into the graph isomorphism problem, after trying to use vertex degree values as anchors for determining isomorphism (Of course failing with regular graphs), the next obvious target was shortest path values.

However, when looking into using shortest path values to determine isomorphisms, it just seems too obvious. It must not work or else someone whould have discovered this already. I just can't see where this fails. I would appreciate if someone could help me see the failure condition.

With any two given graphs G and G', choose any vertex from G at random. Call this vertex Base. From here you can determine the shortest path information of all other vertices relative to the base. Vertices connected to the base have a shortest path of 1. Vertices connected to vertices connected to the base, but not the base, have a shortest path of 2, and so on. To make communication easier, consider the shortest paths as tiers. Shortest paths of 1 are tier 1, while shortest paths of 2 are tier 2 and so on.

This gives very valuable information. Each of the connections of a given vertex can only fall in one of three categories: Connected to same Tier, Connected to Tier +1, and Connected to Tier -1.

There is a non-exponental number of combinations, so it can't require exponential running time to solve. By going through both graphs and using all the vertices as bases, you get invarient graph information that can be used to create an ordered grouping that can be compared to another graph's, to determine if the two are the same.

As I said before, what am I missing? It just can't be that simple, can it?

  • 0
    Also, regarding sufficiency, if you know the connections via tiers, I would imagine you could draw the graph. Take your base. Draw it's connections, draw the tier 1 connections following the same tier/next tier rules, then the tier two connections with consideration to it's connections to lower/same/higher tiers. When finished with each base, you should be able to match each drawing to a drawing from an isomorphic graph. If the method works. But I really cant imagine it works, It just doesn't seem powerful enough for what it does.2012-12-26

1 Answers 1

7

This approach fails on strongly regular graphs. Examples of these can be constructed from Latin squares, as follows. Assume $L$ is an $n\times n$ Latin square with entries from $N=\{1,\ldots,n\}$. The vertices of the associated Latin square graph are the $n^2$ ordered pairs in $N\times N$; two vertices $(i,j)$ and $(k,l)$ are adjacent if $i=k$ or $j=l$ or $L_{i,j}=L_{k,l}$. Any two distinct non-adjacent vertices are at distance two, and are joined by exactly six paths of length two.

  • 0
    @thams andrews: Multiplication tables of non-isomorphic groups will work, e.g., $\mathbb{Z}_2^2$ and $\mathbb{Z}_4$. More generally any pair of srg's with the same parameters; Latin square graphs are just the easiest to describe.2012-12-27