Problema del isomorfismo de grafos

El mejor algoritmo teórico actualmente aceptado se debe a Babai y Luks (1983), y se basa en el trabajo anterior de Luks (1982) combinado con un algoritmo subfactorial de V. N. Zemlyachenko (Zemlyachenko, Korneenko y Tyshkevich 1985). El algoritmo ha ejecutado el tiempo 2^{O(√n log n)} para gráficos con n vértices y se basa en la clasificación de grupos finitos simples. Sin CFSG, László Babai (1980) obtuvo primero un límite 2^{O (√n log2 n)} ligeramente más débil, y Babai & Luks (1983) lo extendió a los gráficos generales. La mejora del exponente √n es un gran problema abierto; para gráficos fuertemente regulares esto fue hecho por Spielman (1996). Para hipergrafos de rango limitado, Babai y Codenotti (2008) obtuvieron un límite superior subexponencial que coincide con el caso de los gráficos.

En noviembre de 2015, Babai anunció un algoritmo de tiempo quasipolynomial para todos los gráficos, es decir, uno con tiempo de ejecución ${\displaystyle 2^{O((\log n)^{c})}}$ para algunos arreglados ${\displaystyle c>0}$ . El 4 de enero de 2017, Babai se retractó del reclamo cuasi-polinomial y declaró un límite de tiempo sub-exponencial en su lugar después de Harald Helfgott descubrió un defecto en la prueba. El 9 de enero de 2017, Babai anunció una corrección (publicada en su totalidad el 19 de enero) y restauró el reclamo cuasi polinomial, con Helfgott confirmando la solución. Helfgott afirma además que uno puede tomar c = 3, por lo que el tiempo de ejecución es 2^{O((log n) 3)}. La nueva prueba aún no ha sido revisada por completo.

Existen varios algoritmos prácticos competitivos para el isomorfismo gráfico, como los debidos a McKay (1981), Schmidt y Druffel (1976) y Ullman (1976). Si bien parecen funcionar bien en gráficos aleatorios, una desventaja importante de estos algoritmos es su rendimiento de tiempo exponencial en el peor de los casos.

El problema de isomorfismo gráfico es computacionalmente equivalente al problema de calcular el grupo de automorfismo de un gráfico, y es más débil que el problema de isomorfismo del grupo de permutación y el problema de intersección del grupo de permutación. Para los últimos dos problemas, Babai, Kantor y Luks (1983) obtuvieron límites de complejidad similares a los del isomorfismo gráfico.

Varios casos especiales importantes del problema del isomorfismo gráfico tienen soluciones eficientes de tiempo polinomial:

• Árboles

• Gráficos planos (De hecho, el isomorfismo gráfico plano está en el espacio de registro, una clase contenida en P)

• Gráficos de intervalo

• Gráficos de permutación

• Gráficos circulares

• Gráficos de parámetros acotados

• Gráficos de ancho de árbol delimitado

• Gráficos del genus delimitado (Nota: los gráficos planos son gráficos del género 0)

• Gráficos de grado limitado

• Gráficos con multiplicidad de autovalores acotada

• k-Gráficos contractibles (una generalización de grado limitado y género acotado)

• El isomorfismo de conservación del color de los gráficos de colores con multiplicidad de colores delimitados (es decir, como mucho k vértices tienen el mismo color para un k fijo) está en la clase NC, que es una subclase de P

Dado que el problema del isomorfismo gráfico no se sabe que sea NP-completo ni conocido como tratable, los investigadores han tratado de comprender el problema definiendo un nuevo GI de clase, el conjunto de problemas con una reducción de Turing en tiempo polinomial al isomorfismo gráfico problema. Si, de hecho, el problema de isomorfismo gráfico es solucionable en tiempo polinomial, GI sería igual a P.

Como es común para las clases de complejidad dentro de la jerarquía de tiempo polinomial, un problema se llama GI-hard si hay una reducción de Turing en tiempo polinomial desde cualquier problema en GI a ese problema, es decir, una solución de tiempo polinomial a un problema GI-hard produciría una solución de tiempo polinomial al problema del isomorfismo gráfico (y por lo tanto todos los problemas en GI). Un problema ${\displaystyle X}$ se llama completo para GI, o GI-complete, si es tanto GI-hard y una solución de tiempo polinomial al problema GI produciría una solución de tiempo polinomial para ${\displaystyle X}$.

El problema del isomorfismo gráfico está contenido tanto en NP como en co-AM. GI está contenido en y bajo para Parity P, así como también está contenido en el SPP de clase potencialmente mucho más pequeño. Que se encuentre en la Paridad P significa que el problema del isomorfismo gráfico no es más difícil que determinar si una máquina de Turing no determinista de tiempo polinomial tiene un número par o impar de rutas de aceptación. GI también está contenido en y bajo para ZPP^NP. Esto esencialmente significa que un algoritmo eficiente de Las Vegas con acceso a un oráculo de NP puede resolver el isomorfismo gráfico tan fácilmente que no obtiene poder de poder hacerlo en tiempo constante.

Manuel Blum y Sampath Kannan (1995) han mostrado un verificador probabilístico para programas de isomorfismo gráfico. Supongamos que P es un procedimiento reclamado de tiempo polinomial que verifica si dos gráficos son isomorfos, pero no es de confianza. Para verificar si G y H son isomorfos:

• Pregunte a P si G y H son isomorfos.

• Si la respuesta es 'sí':

• Intente construir un isomorfismo usando P como subrutina. Marque un vértice u en G y v en H, y modifique los gráficos para que sean distintivos (con un pequeño cambio local). Pregunte a P si los gráficos modificados son isomorfos. Si no, cambie v a un vértice diferente. Continúa buscando

• O el isomorfismo se encontrará (y se podrá verificar), o P se contradirá a sí mismo.

• Si la respuesta es "no":

• Realice las siguientes 100 veces. Elija aleatoriamente G o H, y permute aleatoriamente sus vértices. Pregunte a P si el gráfico es isomorfo a G y H. (Como en el protocolo AM para el gráfico no isomorfismo).

• Si alguna de las pruebas falla, juzgue a P como un programa inválido. De lo contrario, responda "no".

Este procedimiento es polinomial y da la respuesta correcta si P es un programa correcto para el isomorfismo gráfico. Si P no es un programa correcto, pero responde correctamente en G y H, el verificador dará la respuesta correcta o detectará el comportamiento no válido de P. Si P no es un programa correcto y responde incorrectamente en G y H, el verificador detectará el comportamiento inválido de P con alta probabilidad, o responderá incorrectamente con probabilidad 2^-100.

En particular, P se usa solo como caja negra.