Est-ce que «une permutation p est un automorphisme d'un graphe dans mon ensemble?» NP-complet?

Supposons que nous ayons un ensemble S de graphes (graphes finis, mais un nombre infini d'entre eux) et un groupe P de permutations qui agit sur S.

Instance: Une permutation p dans P.

Question: Existe-t-il un graphe g dans S qui admette l'automorphisme p?

Ce problème est-il NP-complet pour certains ensembles S?

Il serait facile de vérifier qu'un graphe admet la permutation p (ie certificat). De plus, il est facile de trouver des exemples de S où le problème n'est pas NP-complet, comme S étant l'ensemble de graphes complets, d'où la réponse est toujours oui.

Remarque: je ne suis pas vraiment intéressé par le type de graphiques qu'il s'agit; si vous le souhaitez, ils peuvent être non simples, dirigés, colorés, etc.

ADDENDA: Le problème que je regarde actuellement est de classer quels isotopismes sont des autotopismes de carrés latins (qui peuvent également être interprétés comme un type spécial d'automorphisme de graphe).

Étant donné un carré latin L (i, j), nous pouvons construire un graphique de la manière suivante:

L'ensemble des sommets est l'ensemble des cellules (i, j) de la matrice et
Il y a un bord entre distinct (i, j) et (i ', j') chaque fois que i = i 'ou j = j' ou L (i, j) = L (i ', j').

Un tel graphique est appelé un graphique carré latin (voir par exemple cet article de Bailey et Cameron http://designtheory.org/library/encyc/topics/lsee.pdf ). Nous pouvons interpréter un autotopisme d'un carré latin comme un automorphisme du graphe carré latin. Soit donc S l'ensemble des graphes latins carrés formés à partir des carrés latins d'ordre n. Donc la question qui m'intéresse est:

Étant donné une permutation p, p est-il un automorphisme d'un (ou plusieurs) des graphes de S?

Mon sentiment est que c'est une question difficile à répondre en général - j'écris actuellement un article de plus de 30 pages sur le sujet (avec 2 co-auteurs). En fait, la plupart du temps, c'est facile (la plupart du temps c'est "non"), mais il y a des cas difficiles.

Je suis donc intéressé à trouver des problèmes de décision qui seraient liés à la "classification de symétrie". Ils n'ont pas vraiment besoin d'être liés aux carrés latins, j'espère simplement utiliser ces techniques pour répondre à la question des carrés latins.

cc.complexity-theory graph-theory np-hardness automorphism Douglas S. Stones
la source

Je ne sais pas si je comprends bien le problème. Pouvez-vous donner un exemple de S et P (et l'action de groupe de P sur S)? Un exemple qui rend le problème non trivial (ni tout oui ou tout non) aidera à comprendre le problème.

Tsuyoshi Ito

Dans l'exemple des graphes complets, ce que je ne comprends pas, c'est comment une permutation sur k points agit sur le graphe complet sur n points, où k ≠ n (surtout si k> n).

Tsuyoshi Ito

J'ai réussi à me tromper en pensant que je comprenais le problème, mais j'ai décidé que non. Le groupe de permutations S agit-il sur les graphes de la famille P, ou n'agit-il que potentiellement sur les graphes de la famille P?

Niel de Beaudrap

Un problème ici est que nous devons choisir un ensemble

pour lequel le test d'appartenance est dans NP.

S

$S$

Emil

J'ai ajouté un peu plus de contexte dans la réponse. En fait, en général, je ne me soucie pas vraiment de savoir si le groupe agit sur S, aussi longtemps que nous pouvons répondre "cette permutation est-elle un automorphisme de ce graphique?" Dans le cas des carrés latins, nous pouvons l'interpréter comme une action de groupe.

Douglas S. Stones

Réponses:

Prenez n'importe quel langage (qui se compose de chaînes binaires). Construisez l'ensemble de graphiques comme suit: $L$ $S$

Pour chaque chaîne avec , on a la courbe en , avec l'ensemble de noeuds et les fronts suivants: si le bit de vaut , alors les nœuds et $x \in L$ $|x| = n$ $G_x = (V_x,E_x)$ $S$ $V_x = \{1,2,...,3n\}$ $i$ $x$ $0$ $3i-2$ sont adjacents, sinon et sont adjacents. Il n'y a pas d'autres bords. $3i-1$ $3i-2$ $3i$

Maintenant , nous allons une permutation de . On suppose que est un automorphismes d'un graphe dans . C'est, est un automorphisme de pour certains . Laissez . Considérons les deux cas suivants: $p$ $\{1,2,...,3n\}$ $p$ $S$ $p$ $G_y$ $y \in L$ $i \in \{1,2,...,n\}$

, , . Ensuite, nous devons avoir le bit de égal à . $p(3i-2) = 3i-1$ $p(3i-1) = 3i-2$ $p(3i) = 3i$ $i$ $y$ $0$
, , . Ensuite, nous devons avoir le bit de égal à . $p(3i-2) = 3i$ $p(3i-1) = 3i-1$ $p(3i) = 3i-2$ $i$ $y$ $1$

Donc, si nous pouvons résoudre la question "est un automorphisme donné de certains ", nous pouvons également résoudre la question "est une chaîne donnée dans ". De plus, si nous pouvons faire le premier en, disons, le temps polynomial dans , on peut faire ce dernier en temps polynomial en ainsi que. $p$ $G \in S$ $y$ $L$ $|p|$ $|y|$

Maintenant, vous pouvez simplement laisser être votre problème NP-hard préféré. Ou le problème de l'arrêt ... $L$

Jukka Suomela
la source

Et pour répondre à la question d'origine: Soit

un problème NP-complet, et vous aurez un

tel que le problème d'automorphisme soit NP-complet. Le certificat pour une réponse « oui » est un

tel que

est le automorphisme de

, ainsi que le certificat pour

L

$L$

S

$S$

G_{y} \in S

$G_y \in S$

p

$p$

G_{y}

$G_y$

y \in L

$y \in L$

Jukka Suomela

@Jukka: Une façon de rapprocher la question de la motivation d'origine des graphes carrés latins est d'exiger que l'ensemble

des graphes soit fermé sous isomorphisme. Il s'agit également d'une restriction tout à fait naturelle. L'ensemble

vous construisez à partir d'un langage arbitraire

n'est pas fermé sous isomorphisme et, dans ce sens très spécifique, est un peu contre nature. Je ne vois pas comment modifier votre construction pour satisfaire cette contrainte, mais je pense que ce serait très intéressant si cela pouvait être fait.

S

$S$

S

$S$

L

$L$

Joshua Grochow

@Joshua: Je pense qu'il est possible de modifier la construction, par exemple comme suit: les graphes et les permutations que nous utilisons dans les requêtes sont constitués de cycles disjoints . Plus en détail,

contient un cycle de longueur

si le bit

est égal à

. De même, pour déterminer si

, construisons une permutation

qui contient un cycle de longueur

ssi bit

G_{x}

$G_x$

2 i + a + 1

$2i+a+1$

i

$i$

x

$x$

a

$a$

y \in L

$y \in L$

p

$p$

2 i + a + 1

$2i+a+1$

i

$i$ de

est égal à

y

$y$

a

$a$ . (J'ai peut-être négligé certains détails, mais je pense que l'idée de base devrait fonctionner ...)

Jukka Suomela

@Jukka: Nice. Je crois que la nouvelle construction fonctionne comme écrite (en supposant que nous ne permettons à

d'agir que sur des graphiques avec exactement

sommets, et non sur des graphiques avec plus de

sommets).

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

Joshua Grochow du

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$