Coloreando grafos a través del espejo
Abstract
En la Escuela Superior de Ingeniería de la Universidad de Cádiz, los conflictos ocasionados por las coincidencias en los horarios de exámenes se han resuelto durante la última década modelándolos mediante la coloración de grafos. La dificultad matemática de este tipo de tareas es histórica. Sus raíces se remontan al siglo XIX con la formulación de la conjetura de los cuatro colores, la cual establecía que esta cantidad era suficiente para colorear cualquier mapa evitando que países fronterizos compartieran el mismo color. La comunidad científica tardó un siglo entero en poder demostrar su veracidad. Esta dificultad inherente quedó ratificada en la segunda mitad del siglo XX; desde el punto de vista de la complejidad computacional, el problema general de calcular el número cromático para un grafo cualquiera —es decir, determinar la cantidad mínima de colores necesarios para que ningún par de elementos conectados comparta el mismo— es NP-completo. A pesar de esta gran barrera teórica, durante décadas se han desarrollado multitud de resultados aplicables a la resolución de conflictos prácticos, como la asignación de recursos y la propia planificación de horarios académicos.
Como en todo problema NP, no se espera poder resolver instancias muy grandes de forma trivial. En nuestro caso de los conflictos de exámenes, diseñamos inicialmente un algoritmo voraz (greedy) sencillo que funcionaba de manera adecuada en la práctica. Un día, incapaz de superar la complejidad del problema, el algoritmo dejó de converger a una solución. Este obstáculo nos obligó a estudiar con detalle la topología del problema y explorar resultados matemáticos avanzados que pudieran asistirnos. Esto nos empujó a caer por la madriguera hacia un viaje fascinante por el mundo de los coloreados por listas, las extensiones de precoloreados, los grafos de Berge, los grafos perfectos, los grafos cordales y otros especímenes. Con este nuevo conocimiento, creemos haber mejorado el algoritmo… o tal vez no. Esta charla cuenta la historia de ese viaje.
Speaker
Luis Lafuente
Universidad de Cádiz
