3
$\begingroup$

What are the best known Graph-Isomorphism algorithms for below graph classes-

1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive.

Provide run-times/time complexity of algorithm, if possible.

Also, If a graph has large number of automorphisms like above graphs, is it helpful to determine isomorphism? Is there any such relationship in current literature ?

$\endgroup$
1
  • $\begingroup$ Questions older than 60 days cannot be migrated. You can re-ask it (but give a link to this question if you do). $\endgroup$ Oct 28 '16 at 14:47
1
$\begingroup$

Graph Isomorphism of Vertex Transistive Graphs is GI Complete(Graph-Isomorphism Complete) .

Vertex-transitivity test can be done by testing graph isomorphism $n−1$ times: Make two copies $G$ and $G'$ of your graph, with special anchors (like paths of length $n+1$) at $u \in V(G)$ and $v \in V(G')$. There is an isomorphism between $G$ and $G'$ if and only if the original graph has an automorphism mapping $u$ to $v$. Thus you can test vertex-tansitivity by fixing a vertex $x$, and checking that there are automorphisms mapping $x$ to all the other vertices. So, if vertex-transitivity test can be done in polynomial time, then so is isomorphism test for vertex-transitive graphs (there exists a polynomial time reduction). This is because two vertex-transitive graphs are isomorphic if and only if their disjoint union is vertex-transitive, thus computational complexity of graph isomorphism for vertex-transitive graphs lies in the same class of graph isomorphism .

See a related paper by Jajcay, Malnič, Marušič [1] , it says -

For a given finite graph $\Gamma$, it is decidedly hard to determine whether $\Gamma$ is vertex-transitive, and the ultimate answer comes usually only after a substantial part of the full automorphism group of $\Gamma$ has been determined.

So, saying a graph is vertex transitive gives no extra information, benefits to test isomorphism. One has to find out the automorphism set of the Vertex Transistive Graph . Determining a generating set for automorphism group of a given graph is GI Complete (Due to Rudi Mathon [2]), it means that the determining the a generating set for automorphism group of a given graph is equal to solving graph isomorphism problem .

Same argument could be used to edge-transitive, arc-transitive (or symmetric) , distance-transitive graph.

Addition:

    1.

Thank you very much for your edit. Your reduction from VT to Iso is elegant and can be improved to a many-one reduction: simply ask for graph isomorphism, once, of the disjoint union of all the copies. Next, you provide a reduction from VTIso (vertex transitive graph isomorphism) to VT, so we now know that $VTIso \leq VT \leq Iso$. Does the reverse, $Iso \leq VTIso$, hold? I tried finding a reduction for $Iso\leq VTIso$ and for $VT\leq Aut$, but failed.

  • from comment of Lieuwe Vinkhuijzen .

  1. Jajcay, Malnič, Marušič. On the number of closed walks in vertex-transitive graphs. Discrete Math. 307 (2007) 484-493. [doi:10.1016/j.disc.2005.09.039][JMM07]

  2. Mathon, Rudolf (1979), "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (3): 131–132, doi:10.1016/0020-0190(79)90004-8

$\endgroup$
4
  • $\begingroup$ Can you provide a reference for the claim that generating a graph's automorphism group is equivalent to solving graph isomorphism in the case where both graphs are known to be vertex transitive? I cannot find Mathon's result on Google scholar, and even if I could, the fact that in general finding the automorphism group is GI Complete does not mean that this is also true for the case of vertex-transitive graphs. $\endgroup$ Oct 21 '16 at 12:37
  • $\begingroup$ Thank you very much for your edit. Your reduction from VT to Iso is elegant and can be improved to a many-one reduction: simply ask for graph isomorphism, once, of the disjoint union of all the copies. Next, you provide a reduction from VTIso (vertex transitive graph isomorphism) to VT, so we now know that $VTIso \leq VT \leq Iso$. Does the reverse, $Iso \leq VTIso$, hold? This is what we are looking for when we ask whether VTIso is GI-Complete. I tried finding a reduction for $Iso\leq VTIso$ and for $VT\leq Aut$, but failed. $\endgroup$ Oct 27 '16 at 22:40
  • $\begingroup$ You appended my comment to your answer, but did not answer the question whether graph isomorphism reduces to graph isomorphism to vertex-transitive graphs. Also, this question and answer look much more at home at cs.stackexchange or cstheory.stackexchange, but I don't have the power to migrate it. $\endgroup$ Oct 28 '16 at 14:36
  • $\begingroup$ @LieuweVinkhuijzen , I have asked it on CST ME : cstheory.stackexchange.com/questions/36878/… $\endgroup$
    – Michael
    Oct 28 '16 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.