16
$\begingroup$

I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.

Question 1. Let $G$ be a simple undirected graph of order $n$. What is the computational complexity (in terms of $n$) of determining if $G$ is vertex-transitive?

Recall that a graph $G$ is vertex-transitive if $\mathrm{Aut}(G)$ acts transitively on $V(G).$

I am not sure if the above definition allows for a polynomial time algorithm since it can be that the order of $\mathrm{Aut}(G)$ is exponential.

However vertex-transitive graphs have some other structural properties that might be exploited in order to be able to efficiently determine them so I am not sure what is the status of the above question.

Another interesting subclass of vertex-transitive graphs that has even more structure is the class of Cayley graphs. So it is natural to also pose the following related question

Question 2. What is the computational complexity of determing if a graph $G$ is a Cayley graph?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Even though the automorphism group can be super-exponential, I think it can be represented in polynomial space because the minimum number of generators is at most logarithmic in $|\textrm{Aut}(G)|$ $\endgroup$
    – Timothy Sun
    Commented Oct 29, 2012 at 5:46
  • 2
    $\begingroup$ Note that every vertex-transitive graph is a Cayley-Schrier graph: there is some group $G$ with generating set $S$ and subgroup $H$ such that the vertices of the graph are the cosets $G/H$, and two cosets are linked by an edge if some element of $S$ takes one to the other. $\endgroup$
    – Joshua Grochow
    Commented Oct 29, 2012 at 17:55
  • $\begingroup$ Related: mathoverflow.net/questions/156947/… $\endgroup$
    – Peter Heinig
    Commented Mar 21, 2018 at 18:28

1 Answer 1

Reset to default
14
$\begingroup$

I don't have a complete answer, but I think both problems are open.

The paper by Jajcay, Malnič, Marušič [3] is related to your first question. They provide some tools to test vertex-transitivity. They say in the introduction that:

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.

Note that 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.

Also note that if vertex-transitivity test can be done in polynomial time, then so is isomorphism test for vertex-transitive graphs. This is because two vertex-transitive graphs are isomorphic if and only if their disjoint union is vertex-transitive. I believe that complexity of graph isomorphism for vertex-transitive graphs is not known.

For the 2nd question, I found a partial result. A circulant graph is a Cayley graph on a cyclic group. Evdokimov and Ponomarenko [2] show that recognition of circulant graphs can be done in polynomial time. Also the book chapter by Alspach [1, Chapter 6: Cayley graphs, Section 6.2: Recognition] would be interesting for you, although it says that:

We shall ignore the computational problem of recognizing whether an arbitrary graph is a Cayley graph. Instead, we always assume that Cayley graphs have been described in terms of the groups on which they are built, together with the connection sets. For most problems this is not a drawback.

  1. Beineke, Wilson, Cameron. Topics in Algebraic Graph Theory. Cambridge University Press, 2004.
  2. Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835. doi:10.1090/S1061-0022-04-00833-7
  3. 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
Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ In fact, vertex-transitivity can be tested using $n-1$ graph isomorphism tests: fix a vertex $x$, and check that there is an automorphism sending $x$ to any other vertex. $\endgroup$
    – Yuval Filmus
    Commented Oct 29, 2012 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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