# Approximating non-trivial graph automorphism?

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.

• The problem is trivial, the identity permutation is always optimal. – Jukka Suomela Oct 11 '10 at 7:13
• @Jukka, In graph Automorphism problem we seek non-trivial automorphism. Similarly, Here I'm not interested in the identity permutation. – Mohammad Al-Turkistany Oct 11 '10 at 14:59
• I am actually suggesting that you might be asking the wrong question... Perhaps it would help if you told your motivation or application. – Jukka Suomela Oct 11 '10 at 17:11
• 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)? – Mohammad Al-Turkistany Oct 11 '10 at 17:30
• 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. – Derrick Stolee Nov 22 '10 at 18:53

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.

• Indeed, this problem is interesting too. – Mohammad Al-Turkistany Oct 11 '10 at 18:05
• Just a correction: that paper is joint with Arie Matsliah. – arnab Oct 11 '10 at 18:06
• 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}$. – Derrick Stolee Nov 22 '10 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.

• 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. – Mohammad Al-Turkistany Oct 11 '10 at 15:12