Viernes 24/11/2023, 14.30 hs. Aula 27
Titulo: Resultados recientes y principales problemas abiertos sobre la thinnes de un grafo
Resumen:
Gran parte de los problemas de optimización definidos sobre grafos son computacionalmente difíciles. Para estos problemas, resulta natural preguntarse: ¿Para qué subclases de grafos el problema puede resolverse de forma eficiente y para cuáles es intrínsecamente difícil?
Además de la detección de clases particulares y algoritmos ad-hoc para esas clases, desde los años ’80, varios «parámetros de ancho» en un grafo fueron definidos, con el objetivo de abarcar clases de grafos dentro de las cuales problemas NP-completos en general resultaran polinomiales. El primero y más conocido es el treewidth, que mide qué tanto se parece en estructura a un árbol (los árboles son exactamente los grafos de treewidth 1). Saber que una familia de grafos tiene un parámetro de ancho acotado permite diseñar algoritmos eficientes, en general utilizando programación dinámica, para muchos problemas famosos, como el problema de coloreo de grafos o el de conjunto independiente máximo, y versiones más generales de ellos. Más aún, en muchos casos se lograron resultados algorítmicos de aplicación muy general, conocidos como «metateoremas». Un metateorema tiene la forma: «si un problema puede ser expresado en tal lenguaje o con este tipo de restricciones: [tipo correspondiente], entonces puede ser resuelto en tiempo polinomial para grafos de [ancho correspondiente] acotado”.
Los parámetros de ancho en los que estamos trabajando últimamente son la thinness y sus variantes. La thinness fue definida por Mannino, Oriolo, Ricci y Chandran en 2007 en el marco de una aplicación a problemas provenientes de la telefonía celular vinculados con el problema de conjunto independiente en grafos, y mide qué tanto se parece un grafo en estructura a un grafo de intervalos (que son exactamente los grafos de thinness 1).
En esta charla presentaremos los principales resultados conocidos sobre la thinness de un grafo, incluyendo un metateorema para la thinness y algunos resultados muy recientes de trabajos en curso, y las preguntas abiertas en las que planeamos trabajar en los próximos años.