10
$\begingroup$

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.

Improve this question
$\endgroup$
15
  • 3
    $\begingroup$ The problem is trivial, the identity permutation is always optimal. $\endgroup$
    – Jukka Suomela
    Commented 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$
    – Mohammad Al-Turkistany
    Commented 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$
    – Jukka Suomela
    Commented 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$
    – Mohammad Al-Turkistany
    Commented 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$
    – Derrick Stolee
    Commented Nov 22, 2010 at 18:53

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Indeed, this problem is interesting too. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Oct 11, 2010 at 18:05
  • $\begingroup$ Just a correction: that paper is joint with Arie Matsliah. $\endgroup$
    – arnab
    Commented 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$
    – Derrick Stolee
    Commented Nov 22, 2010 at 18:00
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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$
    – Mohammad Al-Turkistany
    Commented Oct 11, 2010 at 15:12

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.