«Petit» isomorphisme graphique

19

En réfléchissant à la complexité du test de l'isomorphisme des graphes asymétriques (voir ma question connexe sur la théorie), une question complémentaire m'est venue à l'esprit.

Supposons que nous ayons une machine de Turing à temps polynomial qui en entrée génère un graphe avec nœuds.1 n G M , n nM1nGM,nn

Nous pouvons définir le problème :ΠM

(GI "minuscule"): Étant donné un graphique , est-il isomorphe à ?G G M , | V |G=(V,E)GGM,|V|

En d'autres termes, nous devons comparer un graphe donné avec un graphe "de référence" de même taille généré par une machine de Turing temps polynomial fixe .M

Pour tous les temps polynomiale machines de Turing , nous avons , et pour beaucoup d'entre eux nous avons . Mais est-ce vrai pour tout ? Le problème est-il connu?Π MN P Π MP MMΠMNPΠMP
M

À première vue, je pensais que chaque devrait être beaucoup plus facile que , car pour chaque il n'y a qu'un seul graphique "de référence" de cette taille et peut-être que les symétries / asymétries des graphiques générés par peuvent être exploitées et un un testeur d'isomorphisme ad hoc peut être construit ... mais ce n'est pas vrai: peut contenir une sorte de machine de Turing universelle temporisée polynomiale qui utilise l'entrée (unaire) pour générer des graphiques de référence complètement différents (dans la structure) comme augmente. G I n M M 1 n nΠMGInMM1nn

Marzio De Biasi
la source
Intéressant, Connaissez-vous un exemple de machine de Turing à temps P qui génère le graphe G M , N ? MGM,N
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Un exemple trivial pour lequel , est un TM M qui sort simplement n sommets isolés (ou un autre est un TM qui sort K n ). Sans perte de généralité, nous pouvons également penser à un modèle dans lequel chaque temps polynomial TM sur alphabet binaire génère un graphique de référence: il suffit de choisir les n 2 premiers bits de la bande après son arrêt, et de l'interpréter comme la matrice d'adjacence de G M , n . ΠMPMnKnn2GM,n
Marzio De Biasi
Pour TM qui garantit que G M , n a du cycle hamiltonien, alors je suppose que Π M est pas dans P . MGM,nΠMP
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Je pense que ce n'est pas vrai: choisissez simplement une MT qui construit simplement un cycle de nœuds: pour tout n le graphe de référence - qui a un cycle hamiltonien - est facilement vérifiable en temps polynomial. Je pense à un exemple non trivial d'un générateur (plutôt simple) pour lequel il semble difficile de montrer que le problème est en P ; mais je veux faire quelques tests avec nauty avant de l'ajouter à la question. nnP
Marzio De Biasi
1
Qu'en est-il du GI "Itsy Bitsy" où pour un M et N fixe, nous devons décider si les deux graphiques générés sur 1 ^ n sont les mêmes? (Ceci est une langue unaire.)
domotorp

Réponses:

6

[Il s'agit plus de quelques commentaires prolongés que d'une réponse.]

1) Si , alors il n'y a pas de limite de polynôme fixe sur la complexité temporelle de tous les Π M , même pour M qui ne prend que du temps, disons n 3 : Si pour tout le temps - n 3 M , Π MD T I M E ( n k ) , alors ce qui suit est un algorithme poly-temps pour GI. En entrée ( G , H ) , construire une machine de Turing M G avec une horloge qui assure que M GGIPΠMMn3n3 MΠMDTIME(nk)(G,H)MGMGne court jamais plus de étapes sur des entrées de taille n , et telles que M G ( 1 | V ( G ) | ) = G , puis résolvent Π M G ( H ) dans le temps O ( n k ) .n3nMG(1|V(G)|)=GΠMG(H)O(nk)

2) Étant donné que pour tout , Π M n'est pas plus difficile que GI, on pourrait penser que le meilleur résultat du type " Π M ne semble pas être en P " que l'on pourrait espérer est un résultat d'exhaustivité GI. Cependant, il me semble peu probable que n'importe quel Π M soit GI-complet, pour au moins les raisons suivantes:MΠMΠMPΠM

  • Tous les résultats d'exhaustivité de l'IG que je connais concernent des classes de graphiques plutôt importantes, plutôt que d'avoir un seul graphique de chaque taille. Même si vous supprimez entièrement l'exigence d'efficacité, je ne connais aucune liste de graphes telle que | V ( G n ) | = n (ou même p o l y ( n ) ) de sorte que le test de l'isomorphisme en G n est GI-complet.G1,G2,|V(Gn)|=npoly(n)Gn

  • Sur une note connexe, la plupart (tous?) Des résultats d'exhaustivité de l'IG ne sont pas simplement des réductions de plusieurs, mais ont la forme suivante: il existe une fonction telle que, étant donné une instance ( G , H ) de GI, ( f ( G ) , f ( H ) ) est une instance de l'autre problème GI-complet. (Ce ne sont que des morphismes poly-temps de relations d'équivalence, ou ce que Fortnow et moi avons appelé «réductions de noyau».) Nous pouvons facilement montrer sans condition qu'il n'y a pas une telle réduction de GI à un Π M (même si vous modifiez la définition pour autoriser Mf(G,H)(f(G),f(H))ΠMMpour produire plusieurs graphiques). Astuce: Obtenez une contradiction en montrant que tout doit avoir son image complètement contenue dans { G M , n } n 0 .f{GM,n}n0

3) Même si l'on pouvait construire sur la base d'une MT universelle comme suggéré dans la question, on peut peut-être encore construire un testeur efficace, mais pas efficacement. Autrement dit, peut-être pour chaque M , Π M est dans P / p o l y ?MMΠMP/poly

Joshua Grochow
la source
1

Je n'ai pas de réponse à votre question mais propose d'envisager une version plus restreinte de pour laquelle nous pouvons montrer qu'elle se situe en P.ΠM

Considérons uniquement les familles de graphes telles que le nombre d'arêtes croît logarithmiquement. Je vais formaliser cela en reformulant la formulation de votre problème, également pour voir si je l'ai bien compris.

Un graphe non orienté à n bords peut être décrit par un n 2 - nGn longues chaînes de bits, simplement concaténer les entrées de la matrice d'adjacence deGdans le triangle supérieur. Il y a donc2 n 2 - nn2n2G graphes possibles surnsommets. Il s'ensuit que toute fonctionf:NNtelle que0f(n)<2n2-n2n2n2nf:NN pour toutndécrit une famille de graphiques. Pour toute fonctionfefficacement calculable,nous définissonsΠfcomme GΠf0f(n)<2n2n2nfΠf

GΠfG is isomorph to the graph described by f(|V(G)|)

Pour un nombre naturel soit b 1 ( x ) le nombre de 1 dans sa représentation binaire. Maintenant, considérons que Π f pour les fonctions efficacement calculables f pour lesquelles il estime que b 1 ( f ( n ) ) O ( log n ) qui est familles de graphes pour lesquels le nombre d'arêtes ne pousse que logarithmiquement, comme indiqué ci - dessus .xb1(x)Πff

b1(f(n))O(logn)

Nous montrons que pour cette classe de fonctions est en P.Πf

fGnf(n)O(logn)O(logn)nO(logn)nparce que nous pouvons essayer toutes les permutations. Ainsi, en utilisant un algorithme gourmand pour attribuer à chaque MCC du graphe d'entrée un MCC dans le graphe de référence, nous pouvons déterminer si les deux graphes sont isomorphes.

John D.
la source
fnGΠfP
En effet, cela semble être un argument plus facile que je ne le pensais. Je vais l'intégrer dans ma réponse.
John D.
Πf
1
O(logn/loglogn)(logn)!(logn)logn=nloglogn2vlogvO(logn/loglogn)O(log2n)