Un avance en la teoría de grafos entusiasma a los matemáticos

Etiquetas

, ,

Artículo publicado por Chris Cesare el 19 de noviembre de 2015 en Nature News

Un algoritmo que acelera la comparación de grafos sería el primer gran avance en las últimas tres décadas.

Un innovador enfoque para solventar un tenaz, aunque elemental, problema de la teoría de grafos — el estudio matemático de las redes de nodos y sus conexiones — puede ser la señal del primer gran avance teórico en la comprensión de este problema en más de 30 años.

Isomorfismo de grafos

Isomorfismo de grafos Crédito: Nature

László Babai, matemático y científico teórico de la computación en la Universidad de Chicago en Illinois, esbozó un avance en dos charlas (vídeo). Ahora van surgiendo los detalles a partir de los matemáticos y científicos de la computación que asistieron.

“Se ha realizado un avance repentino, inesperado y enorme”, comenta Stuart Kurtz, científico de la computación en la Universidad de Chicago.

La charla de Babai esboza una demostración que ilustra que el problema del isomorfismo de grafos — determinar si dos grafos son el mismo — puede resolverse de forma mucho más rápida de lo que anteriormente se pensaba.

Una pregunta natural

Los grafos son unos objetos matemáticos relativamente simples — son representaciones abstractas de redes — que surgen con frecuencia en la física, la química, y las ciencias de la computación. Están definidos por nodos y los vínculos entre los mismos, y pueden describirse como puntos conectados por líneas. El problema del isomorfismo de grafos simplemente pregunta si dos grafos son el mismo, sin importar cómo están dibujados o qué nombres tienen sus nodos.

En cierto sentido, las conexiones entre los nodos son la esencia de los grafos, señala Janos Simon, científico teórico de la computación en la Universidad de Chicago que asistió a las conferencias. “No debería importar qué nombre les des”, explica Simon. Añade que, aparentemente, dar respuesta a la cuestión fundamental debería ser simple, pero los mejores enfoques teóricos no se han desarrollado mucho desde 1983.

Los científicos de la computación a menudo estudian la complejidad de un algoritmo: cuánto tiempo necesita un algoritmo para resolver un problema, o verificar que una solución es correcta. Dos conjuntos conocido de problemas son llamados P — aquellos que pueden resolverse rápidamente — y NP, aquellos que tienen soluciones que pueden comprobarse rápidamente, pero que no necesariamente se hallan rápidamente. El isomorfismo de grafos se sabe que es NP, conteniendo algunos problemas que se cree que necesitan mucho tiempo para resolverse.

Una forma simple de comprobar si dos grafos son iguales es comprobar todas las formas posibles de intercambiar los nombres de los nodos en un grafo, y buscar si encaja con el segundo — un procedimiento muy ineficiente. Pero hay una buena razón para sospechar que el isomorfismo de grafos era más fácil de resolver que esto. Para empezar, los matemáticos han tenido dificultades para encontrar dos grafos que provocasen que el mejor algoritmo de emparejamiento teórico funcionase lentamente.

“Éste era un comportamiento único muy interesante”, comenta Luca Trevisan, científico teórico de la computación en la Universidad de California en Berkeley, que asistió a la segunda charla de Babai. “Por supuesto, ahora, si los resultados del Profesor Babai son correctos, se demuestra que estos patrones de entrada complejos no existen”.

Una ventaja teórica

La nueva demostración de Babai presenta un algoritmo que funciona mucho más rápidamente que los mejores intentos previos, aunque no lo bastante rápidamente para incluir el problema del isomorfismo de grafos en el conjunto de los P.

Se basa en los enfoques anteriores que hallaron las simetrías de un grafo — todas las formas de generar grafos isomórficos cambiando el nombre a los nodos. En su núcleo subyace una nueva rutina que puede resolver con éxito el problema por etapas. Cada etapa reduce sustancialmente el tamaño del problema, ya sea reduciendo el número de nodos que deben ser tenidos en cuenta, reduciendo el número de reordenaciones de nombres que tienen que comprobarse, o descubriendo un objeto altamente simétrico — llamado grafo de Johnson — dentro del grafo que se está poniendo a prueba. El algoritmo funciona de forma recursiva, con cada etapa finalizando en uno de los tres casos, hasta que las partes restantes son lo bastante pequeñas como para comprobarlas por fuerza bruta.

“Éste es un resultado muy profundo”, comenta Jeremy Kun, estudiante de doctorado en matemáticas en la Universidad de Illinois en Chicago que asistió a la primera conferencia de Babai. Tras la charla, Kun escribió una de las primeras entradas en un blog describiendo la demostración de Babai.

Aunque el resultado ha provocado una gran agitación entre los teóricos por las nuevas técnicas que introduce, probablemente tenga pocas consecuencias prácticas. Ya existen algunos algoritmos muy rápidos que pueden discriminar si muchos grafos son isomórficos, incluso aunque no exista una demostración matemática de que son tan rápidos como la de Babai para todos los pares de grafos.

Aún no existe un artículo que describa el resultado, y Babai rechazó realizar una entrevista hasta que un artículo que demuestre el resultado supere la revisión por pares. Sin embargo, tiene previsto dar otra charla el 24 de noviembre.

Referencias

Nature doi: 10.1038/nature.2015.18801

Anuncios

1 pensamiento sobre “Un avance en la teoría de grafos entusiasma a los matemáticos”