El algoritmo determinista más rápido conocido para el problema del isomorfismo gráfico no dirigido

9

¿Cuál es el algoritmo de isomorfismo gráfico no dirigido más rápido conocido?

cc.complexity-theory reference-request graph-algorithms graph-isomorphism bbejot
fuente
2
Creo que es mejor si solo solicita el algoritmo más rápido conocido, y no la exactitud del algoritmo que se proporciona en el documento (en particular, consulte la meta pregunta relevante ). Para mí, el resumen ya es una bandera roja (las conclusiones también parecen contener información falsa).
Juho
1
En general, si un resultado importante para un problema famoso es correcto, aparecería en los blogs de teoría famosos 1 2 y en el artículo de Wikipedia para el problema .
Kaveh
1
El papel no pasa la prueba de olor. Pretende resolver un problema importante, pero apareció en una oscura conferencia. No hay pruebas La corrección se "valida" experimentalmente. Los autores piensan que el isomorfismo gráfico es NP-duro.
Sasho Nikolov
55
@JoshuaGrochow dice que el algoritmo más rápido conocido lleva tiempo en esta respuesta cstheory.stackexchange.com/a/22059/4896 . Creo que el algoritmo es determinista. 2norteIniciar sesión⁡norte
Sasho Nikolov
55
Según dos trabajos recientes sobre el tema: Algoritmo FPT más rápido para isomorfismo gráfico parametrizado por Eigenvalue Multiplicity - 2014 e isomorfismo gráfico aproximado - 2012, el algoritmo más rápido actual tiene un tiempo de ejecución de en gráficos de n-vértices (resultado de Babai y Luks, 1983)2O(norteIniciar sesión⁡norte)
Marzio De Biasi

Respuestas:

3

La investigación sobre el isomorfismo gráfico generalmente ha ido en la dirección de buscar algoritmos eficientes o mejorados para muchas clases especiales de gráficos con algoritmos P-Time para los cuales ha habido mucho progreso, y también un análisis más empírico con software de última generación, por ejemplo Nauty mira un poco el comportamiento promedio y el peor de los casos por separado. para el problema general según esta encuesta de blog realizada por Bennett / Flammia / Harrow, aparentemente un viejo resultado de Babai / Luks puede ser el más conocido.

"Etiquetado canónico del gráfico" por László Babai y Eugene M. Luks STOC 1983 ( artículo aquí ) Esto describe un subexponencial (o, err, ¿cómo decidió Scott llamarlo?), Exp (-n ^ {frac {1} { 2} + c}), algoritmo de tiempo para un gráfico con n vértices. Ahora, como lista de lectura, no recomiendo saltar a este documento todavía, pero solo quería atenuar su optimismo para un algoritmo clásico mostrándole (a) que lo mejor que tenemos en general es un algoritmo de tiempo subexponencial, (b) ese récord se ha mantenido durante casi tres décadas, y (c) que si miras el periódico puedes ver que no es fácil. Abandonar la esperanza a todos los que entran?

Aquí hay otras dos encuestas bastante completas para evaluar el estado del arte, pero tal vez más con una inclinación empírica.

vzn
fuente
Otro punto es que, como en la respuesta de JG, el isomorfismo gráfico tiene profundos vínculos teóricos con el problema del isomorfismo grupal. esto se puede ver en este otro blog en subj por RJLipton, Un acercamiento al isomorfismo gráfico
vzn
Tenga en cuenta que la encuesta de Fortin tiene casi 20 años, lo que es una eternidad en un campo donde, por ejemplo, el concepto de completitud NP tiene solo unos 40 años.
David Richerby
Sí, también noté eso, pero también existe el fenómeno de problemas clave de TCS / hard open que muestran poco progreso importante durante décadas, obviamente también incluyen P vs NP como un ejemplo canónico de eso, y GI se ajusta también como se indicó.
vzn
Parece confundir las afirmaciones "Todavía no hemos resuelto el problema" y "no se han realizado progresos".
David Richerby
2

2Iniciar sesión⁡norteO(1)

Mohammad Al-Turkistany
fuente
Supuestamente se ejecuta en tiempo cuasipolinomial. Incluso si su análisis es defectuoso y es meramente subexponencial, seguirá siendo el algoritmo más rápido.
Stella Biderman