<p>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$:</p>

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

<p>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. </p>

<p>Eldar Fischer and Arie Matsliah (<em>thanks, arnab</em>) have a <a href="http://portal.acm.org/citation.cfm?id=1109591" rel="nofollow">paper in SODA 2006</a> 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. </p>

CC BY-SA 2.5
2010-11-22T18:00:04.753Z
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
CC BY-SA 2.5
2010-10-11T18:05:06.510Z
Indeed, this problem is interesting too.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-11T18:06:52.297Z
Just a correction: that paper is joint with Arie Matsliah.
arnab
CC BY-SA 2.5
2010-10-11T17:56:41.627Z
2010-10-11T18:39:48.160Z
2010-10-11T18:39:48.160Z
Suresh Venkat
<p>A result of Eugene Luks ("<a href="http://ix.cs.uoregon.edu/~luks/iso.pdf" rel="nofollow">Isomorphism of graphs of bounded valence can be tested in polynomial time</a>") 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.</p>

CC BY-SA 2.5
2010-10-11T15:12:38.270Z
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
CC BY-SA 2.5
2010-10-11T07:54:11.900Z
2010-10-11T07:54:11.900Z
Ramprasad
<p>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$</p>

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

<p><strong>Input</strong>: A non-rigid graph $G(V, E)$</p>

<p><strong>Problem</strong>: Find a (non-identity) permutation that minimizes the numbers of violated edges. </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p><strong>Motivation:</strong> 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)? </p>

<p><strong>Edit</strong> April 22</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-22T18:07:10.573Z
If the question is to be interpreted as is written, the optimal value is always 0 as Derrick wrote, and therefore the problem is exactly the same to the graph automorphism problem with the promise that there is a solution.  It has the same complexity as the graph automorphism without this promise.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-22T18:50:43.980Z
@Tsuyoshi, note that the problem is a search problem that finds a permutation closet to the optimal one.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-22T19:03:34.493Z
I know that you are talking about the search version.  Did I suggest otherwise?
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-22T19:12:39.090Z
Oh, I remembered that I had suggested otherwise. :)  First I had written “The answer is always 0” incorrectly.  Then I had edited it to the current comment (the _optimal value_ is always 0).  Therefore, my apologies if you were confused by reading my comment before I edited it.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-22T20:29:07.220Z
@Tsuyoshi, Consider a graph with a unique non-trivial automorphism that moves every node, How hard is it to detect the symmetry of this graph? Does this clarify my motivation?
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-22T20:40:34.697Z
No.  I do not see why studying the problem you stated in this question has any advantage toward your motivation, when compared to studying the usual graph automorphism problem.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-22T20:45:09.763Z
@Tsuyoshi, I guess I should add to my question: while moving at least a constant number of nodes $\Omega(c)$
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-04-22T20:45:19.657Z
Just in case: “minimum” simply means the smallest.  It does not imply any approximation unless you state something like “approximately minimum.”  Therefore what you wrote in the question is not related to approximation, although the title of the question suggests that it should be related to approximation.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-11T07:13:35.600Z
The problem is trivial, the identity permutation is always optimal.
Jukka Suomela
CC BY-SA 2.5
2010-10-11T14:59:49.530Z
@Jukka, In graph Automorphism problem we seek non-trivial automorphism. Similarly, Here I'm not interested in the identity permutation.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-11T16:35:31.070Z
But even then the problem does not seem to be particularly well-defined. I would guess that in many rigid graphs, optimal (or at least near-optimal) solutions are permutations that are formed from an identity permutation by transposing a pair of nodes?
Jukka Suomela
CC BY-SA 2.5
2010-10-11T17:00:00.180Z
Are you suggesting that its easy and there could be a polynomial time algorithm?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-11T17:11:13.920Z
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
CC BY-SA 2.5
2010-10-11T17:30:12.430Z
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
CC BY-SA 2.5
2010-11-22T18:53:15.440Z
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
<cc.complexity-theory><graph-theory><automorphism><symmetry>
Approximating non-trivial graph automorphism?
Mohammad Al-Turkistany
# Approximating non-trivial graph automorphism?

(Asked by: username_0 on 2010-10-11)

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.

**Tags:** cc.complexity-theory, graph-theory, automorphism, symmetry

> **Comments:**
> **username_2**: The problem is trivial, the identity permutation is always optimal.  
> **username_0**: @Jukka, In graph Automorphism problem we seek non-trivial automorphism. Similarly, Here I'm not interested in the identity permutation.  
> **username_2**: But even then the problem does not seem to be particularly well-defined. I would guess that in many rigid graphs, optimal (or at least near-optimal) solutions are permutations that are formed from an identity permutation by transposing a pair of nodes?  
> **username_0**: Are you suggesting that its easy and there could be a polynomial time algorithm?  
> **username_2**: I am actually suggesting that you might be asking the wrong question... Perhaps it would help if you told your motivation or application.  
> **username_0**: 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)?  
> **username_3**: 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.  
> **username_1**: If the question is to be interpreted as is written, the optimal value is always 0 as Derrick wrote, and therefore the problem is exactly the same to the graph automorphism problem with the promise that there is a solution.  It has the same complexity as the graph automorphism without this promise.  
> **username_0**: @Tsuyoshi, note that the problem is a search problem that finds a permutation closet to the optimal one.  
> **username_1**: I know that you are talking about the search version.  Did I suggest otherwise?  
> **username_1**: Oh, I remembered that I had suggested otherwise. :)  First I had written “The answer is always 0” incorrectly.  Then I had edited it to the current comment (the _optimal value_ is always 0).  Therefore, my apologies if you were confused by reading my comment before I edited it.  
> **username_0**: @Tsuyoshi, Consider a graph with a unique non-trivial automorphism that moves every node, How hard is it to detect the symmetry of this graph? Does this clarify my motivation?  
> **username_1**: No.  I do not see why studying the problem you stated in this question has any advantage toward your motivation, when compared to studying the usual graph automorphism problem.  
> **username_0**: @Tsuyoshi, I guess I should add to my question: while moving at least a constant number of nodes $\Omega(c)$  
> **username_1**: Just in case: “minimum” simply means the smallest.  It does not imply any approximation unless you state something like “approximately minimum.”  Therefore what you wrote in the question is not related to approximation, although the title of the question suggests that it should be related to approximation.  

---

## 2 answers

### Answer by username_4 on 2010-10-11. Score: 6

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, username_5*) have a [paper in SODA 2006](http://portal.acm.org/citation.cfm?id=1109591) 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.

> **Comments:**
> **username_0**: Indeed, this problem is interesting too.  
> **username_5**: Just a correction: that paper is joint with Arie Matsliah.  
> **username_3**: 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}$.  

---

### Answer by username_6 on 2010-10-11. Score: 3

A result of Eugene Luks ("[Isomorphism of graphs of bounded valence can be tested in polynomial time](http://ix.cs.uoregon.edu/~luks/iso.pdf)") 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.

> **Comments:**
> **username_0**: 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.  

---

