Approximation d'un automorphisme non trivial de graphe?

Graphique automorphismes est une permutation de noeuds du graphe qui induit une bijection sur l'ensemble d'arêtes . Formellement, c'est une permutation de nœuds tels que ssi $E$ $f$ $(u,v)\in E$ $(f(u),f(v))\in E$

Définissez un bord violé pour une permutation comme un bord qui est mappé sur non-bord ou un bord dont la pré-image est non-bord.

Entrée : Un graphe non rigide $G(V, E)$

Problème : recherchez une permutation (sans identité) qui minimise le nombre d'arêtes violées.

Quelle est la complexité de trouver une permutation (sans identité) avec un nombre minimum de bords violés? Le problème est-il difficile pour les graphiques avec un degré maximum limité (sous une certaine hypothèse de complexité)? Par exemple, est-ce difficile pour les graphiques cubiques? $k$

Motivation: Le problème est un relâchement du problème d'automorphisme des graphes (GA). Le graphe d'entrée peut avoir un automorphisme non trivial (par exemple un graphe non rigide). Est-il difficile de trouver un automorphisme approximatif (permutation de placard)?

Modifier le 22 avril

Un graphe rigide (asymétrique) n'a qu'un automorphisme trivial. Un graphe non rigide a une symétrie (limitée) et j'aimerais comprendre la complexité de l'approximation de sa symétrie.

cc.complexity-theory graph-theory automorphism symmetry Mohammad Al-Turkistany
la source

Le problème est trivial, la permutation identitaire est toujours optimale.

Jukka Suomela

@Jukka, Dans le graphique Problème d'automorphisme, nous recherchons un automorphisme non trivial. De même, ici, je ne suis pas intéressé par la permutation d'identité.

Mohammad Al-Turkistany

Je suggère en fait que vous posez peut-être la mauvaise question ... Peut-être que cela aiderait si vous aviez dit votre motivation ou votre candidature.

Jukka Suomela

Le problème est un relâchement du problème d'automorphisme des graphes (GA). Le graphique d'entrée peut avoir un automorphisme non trivial. Est-il difficile de trouver un automorphisme approximatif (permutation de placard)?

Mohammad Al-Turkistany du

Je ne comprends pas pourquoi vous vous limitez aux graphiques non rigides, où la valeur optimale réelle est zéro. Dans les graphiques rigides, le facteur d'approximation peut être plus intéressant.

Derrick Stolee

Réponses:

Je ne comprends pas très bien la motivation. Cependant, permettez-moi de répondre à une question connexe. Dans le framework de test de propriétés, vous disposez de deux graphes ad et souhaitez distinguer deux cas en fonction du paramètre : $G$ $H$ $\epsilon$

$G$ et sont isomorphes $H$
Toute bijection de vers provoque une erreur sur au moins arêtes. $G$ $H$ $\epsilon \binom{n}{2}$

La métrique de complexité est le nombre de sondes aux matrices d'adjacence, et l'objectif est de distinguer les deux cas avec une probabilité élevée en utilisant un nombre sublinéaire de sondes.

Eldar Fischer et Arie Matsliah ( merci, arnab ) ont un article dans SODA 2006 sur précisément ce problème. Bien qu'il ne se connecte pas directement à votre problème, il peut être un moyen de formuler un problème possible et pourrait même vous fournir des techniques utiles.

Suresh Venkat
la source

En effet, ce problème est également intéressant.

Mohammad Al-Turkistany,

Juste une correction: ce document est conjoint avec Arie Matsliah.

arnab

Si nous considérons et comme le même graphique, nous pouvons être assurés d'avoir moins de collisions dans une permutation non triviale en échangeant n'importe quelle paire de sommets. C'est beaucoup moins que .

G

$G$

H

$H$

2 n

$2n$

ϵ (\binom{n}{2})

$\epsilon{n\choose 2}$

Derrick Stolee du

Un résultat d'Eugene Luks ("L' isomorphisme des graphes de valence bornée peut être testé en temps polynomial ") montre que l'isomorphisme (ou automorphisme) des graphes pour les graphes en degrés bornés est en temps polynomial. Par conséquent, si vous recherchez un quasi-automorphisme (non-identité, comme l'a souligné Jukka) pour des graphiques cubiques qui ne sont pas rigides, nous pouvons utiliser l'algorithme de Luks et prendre tout automorphisme non trivial dans le graphique.

Ramprasad
la source

J'ai parcouru le document et je crois comprendre qu'il résout le problème de décision de degré borné GA en temps polynomial. Ma question est un problème d'optimisation. De plus, vous ne pouvez pas exclure des graphiques rigides.

Mohammad Al-Turkistany,