Investigadores en computación desarrollan nueva solución para coloreo de grafos

El artículo “Three-coloring and list three-coloring of graphs without induced paths on seven vertices” (Tres-coloreo y tres-coloreo con listas de grafos sin caminos inducidos de siete vértices), será publicado próximamente en la revista científica “Combinatorica”, una de las revistas internacionales más prestigiosas del área.

El trabajo inédito fue desarrollado a fines de 2016 por Flavia Bonomo, profesora e investigadora del DC, junto a otros prestigiosos investigadores de universidades extranjeras. Este aporte extiende la frontera de la polinomialidad del problema de 3-coloreo, y aporta a la clasificación de para qué estructuras prohibidas el problema es P (polinomial) o NP-completo (no determinístico polinomial completo).

Los investigadores desarrollaron un algoritmo polinomial para una versión general de coloreo con 3 colores en grafos sin caminos inducidos de 7 vértices. La técnica del algoritmo podría llegar a ser adaptada a casos de grafos sin caminos inducidos de 8 vértices, o en general sin caminos inducidos de t vértices con t un número fijo, aunque la adaptación no es inmediata.

El problema de coloreo de grafos nace en 1852 con la famosa conjetura (hoy teorema) de los cuatro colores, que afirma que todo mapa en el plano puede ser coloreado con cuatro colores de manera tal que dos regiones que comparten una frontera mayor a un punto no reciban el mismo color. Es un problema ampliamente estudiado en el área de teoría de grafos y sobre todo desde el punto de vista computacional, por su gran cantidad de aplicaciones. Además de para el coloreo de mapas, sirve de modelo para problemas de asignación de frecuencias, asignación de recursos, producción industrial y logística.

Para conocer más sobre el artículo Tres-coloreo, el DC entrevistó a Flavia Bonomo:

¿Qué problema pretende resolver este nuevo trabajo?

El problema que nosotros resolvimos es el de colorear un grafo con 3 colores (o asegurar que no se puede), que ya es un problema complejo en grafos generales. Para esta clase de grafos particular, sin caminos inducidos de 7 vértices, encontramos un algoritmo eficiente que lo resuelve. Cuando se sabe que un problema es difícil en el caso general, resulta natural analizarlo en clases particulares. Por ejemplo, otra clase de grafos en la que hace tiempo se sabe resolver el problema de coloreo en forma eficiente es aquella conocida como “grafos de intervalo”, porque las incompatibilidades vienen de intervalos de tiempo que se superponen. A nivel académico, el trabajo extiende la frontera de la polinomialidad del problema de 3-coloreo, que es uno de los más estudiados en grafos, y aporta a la clasificación de para qué estructuras prohibidas el problema es P o NP-completo.

¿Un ejemplo?

Pensemos en el problema de asignar habitaciones de hotel a reservas. Tenemos una limitación básica: no podemos aceptar más reservas para un mismo día que la cantidad de habitaciones que tiene el hotel. Pero no sólo eso. Idealmente uno querría asignar una única habitación a una estadía, de días consecutivos, y no estar mudando a la gente de habitación cada día. Ese problema puede ser modelado como un problema de coloreo de grafos: las habitaciones son los colores, las estadías vértices de un grafo, y la incompatibilidad entre dos reservas por días en común son las aristas. Dos vértices son adyacentes cuando las correspondientes estadías comparten algún día. Como en general hay más de dos habitaciones en un hotel, estamos modelando la gestión de reservas como un problema NP-completo, algorítmicamente difícil. Sin embargo los hoteleros se las arreglan bastante bien. ¿Por qué? El punto es que uno no puede obtener cualquier grafo arbitrario a partir de intersección de períodos de días consecutivos. Los grafos obtenidos son justamente grafos de intervalos, y hay un algoritmo muy simple y eficiente para resolver coloreo en esa clase de grafos.

Es más, se puede demostrar que cualquier conjunto de reservas es gestionable exitosamente siempre y cuando no existe un día para el cual se tengan más reservas que habitaciones. En teoría de grafos, esa propiedad tiene que ver con que los grafos de intervalos son “grafos perfectos”, otra clase especial de grafos.

Este ejemplo nos muestra que a veces tiene sentido para problemas que son NP-completos en la clase general de grafos, estudiarlos en clases de grafos particulares e intentar conseguir algoritmos eficientes para el problema restringido, porque alguna aplicación concreta podría caer dentro de una de esas clases.

El problema de 2 colores es fácil de resolver porque pertenece a la familia de problemas polinomiales. ¿Por qué trabajar con 3 colores o más resulta un problema difícil?

Para el problema de colorear un grafo con un conjunto de 3 colores, o de 4 colores, o en general de k colores con k un número dado, no se conoce ningún algoritmo polinomial. Los algoritmos más simples demoran un tiempo exponencial en el tamaño del grafo, proporcional a 3x para 3 colores y un grafo de x vértices. Se conocen algoritmos más sofisticados y más eficientes, pero de todas maneras su tiempo de ejecución para algunas instancias no puede ser acotado por un polinomio en x.

Lo que estamos estudiando son grafos que no poseen en su estructura un camino inducido de 7 vértices (7 vértices unidos en forma consecutiva y sin ningún “atajo”). En grafos que no tienen esa estructura lo que nosotros mostramos es que el problema es polinomial.

Si prohibís caminos inducidos de 3 vértices lo que te queda es que es una unión de grafos completos. Por ello es bastante trivial el problema. Si prohibís caminos de 4 vértices no es tan trivial pero es polinomial para cualquier cantidad de colores. Lo que se probó es que para cualquier cosa que prohíbas que no sea un camino o una unión disjunta de caminos, el problema se mantiene NP-completo.

¿Cómo se relaciona esto con la pregunta de si es P=NP?

Hay un montón de problemas para los cuales no se conocen algoritmos polinomiales, problemas que se llaman NP (no determinístico polinomial). Es decir, admiten un algoritmo polinomial pero no determinístico. Si alguien viene y te da la solución con el coloreo, lo podés verificar (que es válido y que tiene solo 3 colores) en tiempo polinomial. Pero no sabés producir una solución concreta con un algoritmo en tiempo polinomial. Sino que verificás una solución dada.

Lo que no se respondió es si existe un algoritmo polinomial para resolver esos problemas NP. La pregunta del millón de dólares (tan famosa que aparece en un episodio de Los Simpson) es una pregunta del siglo XX que se había planteado a principios de 1900. Para todo problema que admita que una solución pueda ser verificada en tiempo polinomial, en realidad existe un algoritmo polinomial que podría encontrar esa solución. Eso no se sabe. Por eso uno asume que existen estos problemas difíciles NP. Hay una clase de problemas que se llaman NP-completos, que se probó que son los más difíciles de la clase NP. Si uno resuelve uno de ellos, resolvería todos los problemas en NP. El Teorema de Cook fue el primero en demostrar que existe un problema con esta propiedad (el teorema dice que el problema de satisfacibilidad booleana (SAT) es NP-completo).

En nuestro trabajo, el problema es de NP. Por eso uno trata de clasificar las instancias para distintas clases de grafos para ver si el problema es polinomial o es NP-completo. El problema de coloreo tiene tantas aplicaciones que el hecho de encontrar clases donde se pueda resolver en tiempo polinomial es relevante. Claramente es útil porque el día de mañana puede aparecer una aplicación donde nunca se presente esa estructura de incompatibilidad que forma caminos entre 7 vértices (o sea, no puede haber 7 vértices encadenados consecutivamente sin que haya un atajo). Esa es la clase de grafos sin caminos inducidos de 7 vértices.

Por último, ¿qué otros ejemplos de aplicaciones puede haber con coloreo?

Otro problema para trabajar en coloreo de grafos con estructuras prohibidas es la asignación de frecuencias de antenas. En este caso, necesitamos que las antenas que estén cercanas no compartan la misma frecuencia, sino si se cruzan las ondas hacen interferencia.

Aplicado a un grafo, las frecuencias son los colores, las antenas son los vértices y si tenemos dos antenas cercanas geográficamente eso constituiría una arista. Entonces si las antenas fueran todas del mismo tipo y tienen un radio de interferencia que es el mismo, no puede pasar que uno tenga una antena que interfiere con otras 6 antenas y ningún par de esas 6 antenas interfiere entre sí. La estructura prohibida en este caso es otro grafo que se llama “estrella de 6 puntas”.

De aplicaciones concretas aparecen naturalmente las estructuras prohibidas. Una estructura prohibida de grafos planares (grafos que vienen de modelar el problema de pintar mapas) es la del juego de las “3 casitas y agua, luz y gas”. Uno tenía que conectar las 3 casitas con los 3 servicios sin que se crucen los caños y no se puede. Determinados grafos que surgen con algunas aplicaciones no contienen ciertas estructuras.

Por eso conviene de antemano correr la frontera de la polinomialidad lo más posible y encontrar la mayor cantidad de casos posibles en los que uno puede resolver el problema, en tiempo polinomial.

Otro problema es el de “Pick up & Delivery problem”. Hay un camión que pasa por la ciudad a buscar unos paquetes en un cierto orden y después los reparte en otra ciudad en otro orden. Ese orden puede darse porque quiso minimizar la ruta para buscar todos los paquetes o por los horarios que acordó con los clientes para el retiro. El camión tiene 3 columnas donde entran las cajas que recolecta. En cada columna entran varios paquetes.

El problema es que uno no quiere estar moviendo las cajas que acomodó en un principio en el camión. Una vez que puso el paquete en una columna, debería moverlo solamente para entregarlo. Entonces si tengo dos paquetes en la misma columna del camión que los recogí en cierto orden y los quiero entregar en el mismo orden estoy en problemas. Porque cuando quiera entregar el que quedó más al fondo, voy a tener que mover el que lo está tapando. Entonces esas cajas deberían ir en diferentes columnas del camión. En este caso las columnas serían los colores, los paquetes serían los vértices y las incompatibilidades se dan por dos ítems que no pueden ir en la misma columna, si el orden de recolección es el mismo que el orden de entrega.

Esta aplicación se usa muchísimo en logística. Se utilizan grafos de permutación cuyo coloreo es polinomial. Pero en definitiva los grafos de intervalos de tiempo y los grafos de permutación aparecieron mucho antes del problema de los hoteles, frecuencias y camiones. Al momento de surgir estos problemas, ya había soluciones diseñadas en teoría de grafos.

Y modelar con coloreo es algo bastante común para los ingenieros e informáticos que están generalmente en las empresas. Lo que quizás es más complicado, es empezar a pensar si el grafo es un grafo general o cae en una clase particular. Por ejemplo, el problema de Pick up & Delivery de los camiones, lo vimos porque nos tocó evaluar un trabajo para un congreso y nos dimos cuenta de que ellos usaban una heurística cuando en realidad el grafo obtenido era un grafo de permutación y admitía un algoritmo exacto y eficiente. Lo que generalmente está pendiente en la industria, es poder clasificar el tipo de problema y en qué clase de grafos entra.