14
$\begingroup$

While reading the question Examples where the uniqueness of the solution makes it easier to find, a new (easier?) question came to my mind: actually we don't know if the Graph Isomorphism ($GI$) problem is in $P$.

But what happens if we assume that both $G_1$ and $G_2$ are asymmetric (i.e. both have only the trivial (identity) automorphism) ? Does the problem become easier (polynomial time)?

Note: the problem cannot be harder than Graph Automorphism ($GA$), because there is a quick reduction: just use $GA$ on $G_1 \cup G_2$, if the answer is yes then the two graphs are isomorphic (see also Johannes Köbler, Uwe Schöning, Jacobo Torán: Graph Isomorphism is Low for PP. 401-411).

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ With probability approaching 1 as n grows, your graph has only the trival automorphoism by Kolmogorov complexity. $\endgroup$
    – Chad Brewbaker
    Commented Apr 13, 2014 at 0:31
  • 1
    $\begingroup$ +1 Nice question, your question potentially leads to an attack on P vs NP. Try to prove that no Turing reduction exist from $GA$ to your problem. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Apr 13, 2014 at 7:52
  • 4
    $\begingroup$ This problem is known as the rigid graph isomorphism problem. If it can be solved in polynomial time or not is widely open. There is some work trying to attack it via quantum algorithms, for instance, by reducing it to the hidden shift problem ( arxiv.org/abs/quant-ph/0510185) but the results are mostly negative showing that the tried techniques don't work. $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Apr 13, 2014 at 14:53
  • 2
    $\begingroup$ It is possible to rigidify any graph so that it has only a single endomorphism (and hence automorphism), by attaching mutually rigid graphs to each vertex. This implies a Turing reduction from GI to deciding isomorphism of asymmetric graphs. Alas, it is not polynomial. $\endgroup$
    – András Salamon
    Commented Apr 13, 2014 at 16:09
  • 1
    $\begingroup$ Well Childs/Wocjan are not alone in using rigid to denote graphs with a single automorphism. There is a survey from Babai from 1994 that already poits that the terminology is not that standard www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf‎ . Also in modern times it rigid has been used in this sense by Jacobo Toran (uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf‎). So it seems that is a matter of whether the author cares about embeddings or not. But I used asymmetric in my answer to avoid confusion. $\endgroup$
    – Mateus de Oliveira Oliveira
    Commented Apr 13, 2014 at 17:59

1 Answer 1

Reset to default
11
$\begingroup$

Upon request of Marzio De Biasi I'm converting my comment into an answer.

A graph is asymmetric (some authors refer to it as rigid) if it has a unique automorphism, i.e., the identity. As pointed out by Chad Brewbacker, most graphs are asymmetric. However the following two questions are open:

1) Is isomorphism of asymmetric graphs in P?

2) Can isomorphism of general graphs be reduced to isomorphism of asymmetric graphs?

Question 1) has received a lot of attention in quantum computing due to the fact that the isomorphism of asymetric graphs can be reduced to the nonabelian hidden subgroup problem and to the non abelian hidden shift problem. However the results are negative, showing that one needs to prepare at least $\Omega(n\log n)$ hidden subgroup states or hidden shift states to have enough information to solve the isomorphism problem.

Improve this answer
$\endgroup$

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.