Gráfico muy regular y completitud GI

16

No se sabe si isomorfismo gráfico (GI) para gráficos fuertemente regulares (SRGS) está en P . ¿Hay alguna pista de que podría o no ser GI -Complete? ¿Hay alguna consecuencia fuerte en tales casos? (Similar a la creencia de que GI puede no ser NP-Completo).

cc.complexity-theory graph-theory graph-algorithms graph-isomorphism structural-complexity DurgaDatta
fuente
66
Personalmente, creo que el problema es estrictamente más fácil que GI, debido al algoritmo de Spielman para SRG, que tiene un exponente más pequeño que el de Luks para los gráficos generales. ¡Parece que hay mucha más estructura! (que en última instancia podría no significar nada)
Timothy Sun
2
Si bien tiendo a estar de acuerdo con @TimothySun, realmente no conozco razones formales para pensar que SRGI es estrictamente más fácil que GI. Por ejemplo, si hay un reducción de GI a SRGI entonces que sería dió un mejor algoritmo para GI que los conocidos actualmente, pero si los golpes reducción de hasta el número de vértices incluso a O ( n 3 / 2 ) , entonces sería No tiene esa consecuencia sorprendente. En cuanto a su segunda pregunta, dudo que haya consecuencias complejas de cualquier problema (que se sabe que reduce a GI) al estar GI completo, ya que no está tan relacionado con la mayoría de las otras clases de complejidad (a diferencia del hecho de que GI siendo NPC colapsa PH). O(norte)O(norte3/ /2)
Joshua Grochow

Respuestas:

11

Creo que todos los resultados GI-completitud conocidos son funtorial (definición en el papel), y Babai ha mostrado recientemente (ITCS 2014, copia de autor libre ) - en base a los límites en la estructura de los grupos de automorfismos de gráficos fuertemente regulares - que no hay funtorial reducción de IG a IG fuertemente regular.

Joshua Grochow
fuente