Graphique très régulier et exhaustivité GI

16

On ne sait pas si isomorphisme de graphes (IG) pour les graphiques fortement réguliers (SRGS) est en P . Y a-t-il des indices qu'il pourrait ou non être GI- Complet? Y a-t-il des conséquences importantes dans de tels cas? (Similaire à la croyance que l'IG peut ne pas être NP-Complete).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
la source
6
Je crois personnellement que le problème est strictement plus facile que GI, à cause de l'algorithme de Spielman pour les SRG, qui a un exposant plus petit que celui de Luks pour les graphiques généraux. Il semble qu'il y ait tellement plus de structure! (ce qui pourrait finalement ne rien signifier)
Timothy Sun
2
Bien que j'ai tendance à être d'accord avec @TimothySun, je ne connais pas vraiment de raisons formelles de penser que SRGI est strictement plus facile que GI. Par exemple, s'il y a un réduction de GI à SRGI alors que produirait un meilleur algorithme pour GI que actuellement connu, mais si les coups de réduction le nombre de sommets même à O ( n 3 / 2 ) alors il pas cette conséquence surprenante. En ce qui concerne votre 2e q., Je doute qu'il y ait des conséquences sur la complexité de tout problème (connu pour se réduire à GI) étant GI-complet, car il n'est pas lié à la plupart des autres classes de complexité (contrairement au fait que le GI étant un PNJ effondre le PH). O(n)O(n3/2)
Joshua Grochow

Réponses:

11

Je crois que tous les résultats connus de l'intégralité de l'IG sont fonctorial (définition dans l'article), et Babai a récemment montré (ITCS 2014, copie gratuite de l'auteur ) - basé sur des limites sur la structure des groupes d'automorphisme de graphiques fortement réguliers - qu'il n'y a pas de fonctorial réduction du GI au GI fortement régulier.

Joshua Grochow
la source