Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such $(u,v)\in E$ iff $(f(u),f(v))\in E$

Define an violated edge for some permutation as an edge that is mapped to non-edge or an edge whose preimage is non-edge.

Input: A non-rigid graph $G(V, E)$

Problem: Find a (non-identity) permutation that minimizes the numbers of violated edges.

What is the complexity of finding a (non-identity) permutation with minimum number of violated edges? Is the problem hard for graphs with bounded maximum degree $k$ (under some complexity assumption)? For instance, Is it hard for cubic graphs?

Motivation: The problem is a relaxation of graph automorphism problem (GA). The input graph may have non-trivial automorphism (e.g. non-rigid graph). How difficult is it to find an approximate automorphism (closet permutation)?

Edit April 22

A rigid (asymmetric) graph has only trivial automorphism. A non-rigid graph has some (limited) symmetry and I'd like to understand the complexity of approximating its symmetry.

  • 3
    $\begingroup$ The problem is trivial, the identity permutation is always optimal. $\endgroup$ Oct 11, 2010 at 7:13
  • 1
    $\begingroup$ @Jukka, In graph Automorphism problem we seek non-trivial automorphism. Similarly, Here I'm not interested in the identity permutation. $\endgroup$ Oct 11, 2010 at 14:59
  • 3
    $\begingroup$ I am actually suggesting that you might be asking the wrong question... Perhaps it would help if you told your motivation or application. $\endgroup$ Oct 11, 2010 at 17:11
  • 1
    $\begingroup$ The problem is a relaxation of graph automorphism problem (GA). The input graph may have non-trivial automorphism. How difficult is it to find an approximate automorphism (closet permutation)? $\endgroup$ Oct 11, 2010 at 17:30
  • 2
    $\begingroup$ I don't understand why you are limiting to non-rigid graphs, where the actual optimal value is zero. In rigid graphs, the approximation factor may be more interesting. $\endgroup$ Nov 22, 2010 at 18:53

2 Answers 2


I don't understand the motivation very well. However, let me provide an answer to a related question. In the property testing framework, you are given two graphs $G$ ad $H$ and wish to distinguish two cases based on parameter $\epsilon$:

  1. $G$ and $H$ are isomorphic
  2. Any bijection from $G$ to $H$ causes error on at least $\epsilon \binom{n}{2}$ edges.

The complexity metric is the number of probes to the adjacency matrices, and the goal is to distinguish the two cases with high probability using a sublinear number of probes.

Eldar Fischer and Arie Matsliah (thanks, arnab) have a paper in SODA 2006 on precisely this problem. While it doesn't directly connect to your problem, it may be a way to a possible problem formulation, and might even provide useful techniques for you.

  • $\begingroup$ Indeed, this problem is interesting too. $\endgroup$ Oct 11, 2010 at 18:05
  • $\begingroup$ Just a correction: that paper is joint with Arie Matsliah. $\endgroup$
    – arnab
    Oct 11, 2010 at 18:06
  • $\begingroup$ If we consider $G$ and $H$ to be the same graph, we can be guaranteed to have fewer than $2n$ collisions in a non-trivial permutation by swapping any pair of vertices. This is much less than $\epsilon{n\choose 2}$. $\endgroup$ Nov 22, 2010 at 18:00

A result of Eugene Luks ("Isomorphism of graphs of bounded valence can be tested in polynomial time") shows that graph isomorphism (or automorphism) for bounded degree graphs is in polynomial time. Hence, if you are looking for some (non-identity, as Jukka pointed out) almost-automorphism for cubic graphs that are non-rigid, then we can use Luks' algorithm and take any non-trivial automorphism in the graph.

  • 1
    $\begingroup$ I skimmed the paper and my understanding is that it solves the bounded degree GA decision problem in polynomial time. My question is an optimization problem. Also, You can not exclude rigid graphs. $\endgroup$ Oct 11, 2010 at 15:12

Your Answer

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

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