Dos científicos informáticos encontraron una idea en un lugar muy inesperado que les resultó útil para un gran avance en la teoría de grafos.
En octubre de 2019, Jacob Holm y Eva Rothenberg estaban hojeando un trabajo que habían publicado unos meses antes y de repente se dieron cuenta de que habían tropezado con algo serio.
Durante décadas, los científicos informáticos han intentado diseñar un algoritmo rápido para determinar si se pueden agregar bordes a un gráfico en particular para que permanezca "plano", es decir, para que sus bordes no se crucen. Sin embargo, nadie ha logrado mejorar el algoritmo publicado hace más de 20 años.
Holm y Rothenberg se sorprendieron al descubrir que en su trabajoExiste una idea que permitió mejorar bastante este algoritmo. Ella "resolvió uno de los principales obstáculos para un algoritmo real", dijo Holm, un científico informático de la Universidad de Copenhague. "Es posible que hayamos revelado completamente este problema".
La pareja se apresuró a trabajar en un nuevo artículo . Lo presentaron en junio en el Simposio de Teoría Computacional de la Association for Computing Machinery, donde detallaron un método para verificar la planaridad de un gráfico, exponencialmente superior a la versión anterior.
“El nuevo algoritmo es verdaderamente magistral”, dijo Giuseppe Italiano , un científico informático de la Universidad de Louis, coautor de un artículo de 1996 que ahora describe el segundo algoritmo más rápido. "Cuando participé en la redacción de ese trabajo, no pensé que esto pudiera suceder".
Los gráficos son colecciones de vértices conectados por aristas. Se pueden usar para etiquetar todo, desde redes sociales hasta redes de carreteras y conductores eléctricos en un tablero. Si en el último caso el gráfico no es plano, los dos conductores se cruzarán, lo que provocará un cortocircuito.
En 1913, aparecieron gráficos planos en un complejo rompecabezas "comunal" sobre tres casas , publicado en The Strand Magazine. La publicación pidió a los lectores que coloquen comunicaciones para tres casas, conectando cada una de ellas con tres vectores de energía: agua, gas y electricidad, para que las comunicaciones no se crucen entre sí. No tarda mucho en darse cuenta de que esta tarea es insuperable.
Sin embargo, en los casos con gráficos más complejos, no siempre es obvio si son planos. Es aún más difícil saber si un gráfico complejo permanecerá plano cuando empiece a agregarle bordes, como es el caso al planificar nuevas carreteras.
Los informáticos han estado buscando durante mucho tiempo un algoritmo que pueda determinar rápidamente si se puede realizar el cambio deseado para que el gráfico permanezca plano, sin pasar por cada una de las partes del gráfico cuando solo se cambia una pequeña parte. El algoritmo de 1996 requirió una serie de pasos para esto, aproximadamente proporcionales a la raíz cuadrada del número de vértices en el gráfico.
"Es mucho mejor que comprobar todo desde cero cada vez, pero no es perfecto", dijo Holm.
El nuevo algoritmo verifica la planaridad en varios pasos proporcionales al cubo del logaritmo del número de vértices en el gráfico; la mejora es exponencial. Holm y Rothenberg de la Universidad Técnica Danesa lograron esta aceleración aprovechando una propiedad especial de los gráficos planos que descubrieron el año pasado.
Para comprender su método, primero debe tener en cuenta que el mismo gráfico plano se puede dibujar de diferentes maneras . Todas las conexiones de estas opciones siguen siendo las mismas, sin embargo, los bordes se pueden ubicar entre sí de diferentes maneras.
Por ejemplo, la figura A se puede cambiar a la figura B invirtiendo el triángulo que forma los vértices 1, 2 y 3 en relación con el borde que conecta los vértices 2 y 3. La parte superior de la figura B también se puede voltear en relación con los vértices 4 y 5, obteniendo la figura C. de manera diferente, pero denotan el mismo gráfico.
Ahora imagina que quieres insertar una nueva arista que conecta dos vértices de un gráfico plano, digamos, los vértices 1 y 6. Para hacer esto, ejecutas una secuencia de volteretas. Desde la posición inicial a la izquierda, en dos giros, puede transferir el vértice 1 al lugar donde se puede conectar al vértice 6 sin cruzar otros bordes.
En un artículo de 2019, Holm y Rothenberg encontraron que algunos dibujos tienen más ventajas para la inserción de bordes que otros. Estos "buenos" patrones solo necesitan unos pocos giros para agregar un nuevo borde sin romper la planitud.
De lo que se dieron cuenta tardíamente en octubre es que un cambio que te acerca a una posición en la que puedes agregar una nueva ventaja también acerca el gráfico a uno de los buenos patrones que ya han definido. Al mostrar que una secuencia de giros inevitablemente acerca el gráfico a los patrones preferidos, se puede crear un nuevo algoritmo para limitar el número de giros que puede necesitar para encontrar una manera de agregar una ventaja (si es posible).
“Nos dimos cuenta muy rápidamente de que con este nuevo análisis el problema podría resolverse
un algoritmo que es extremadamente simple en concepto ”, dijo Holm.
Jacob Holm y Eva Rothenberg El
nuevo algoritmo realiza un giro a la vez en busca de una solución. Como resultado, sucede una de dos cosas: o el algoritmo encuentra una manera de insertar el borde requerido, o el siguiente giro cancela el anterior, después de lo cual el algoritmo concluye que no hay forma de agregar un nuevo borde.
"A este algoritmo lo llamamos vago y codicioso", explicó Rotenberg. "Solo hace los cambios necesarios para acomodar la nueva nervadura".
Su nuevo método se aproxima, pero no coincide, con el rendimiento del mejor algoritmo posible para tales tareas. El nuevo algoritmo también tiene que pasar por demasiados pasos para ser utilizado en la mayoría de las aplicaciones del mundo real; por lo general, los gráficos son lo suficientemente simples como para ser probados con fuerza bruta.
Pero para Holm y Rothenberg, la velocidad del algoritmo no es tan importante como las ideas que lo aceleraron. "Hay consecuencias inmediatas de este entendimiento", dijo Rotenberg.
Italiano cree que eventualmente encontrará usos reales. "Tarde o temprano, seguramente afectará lo que está fuera de la informática con las matemáticas", dijo.
Nadie sabe cuándo pueden aparecer algoritmos aún más rápidos. Esto puede requerir un avance completamente nuevo, o es posible que el ingrediente secreto ya exista en algún lugar, esperando entre bastidores en una pila de investigaciones antiguas.