Un grafo H es menor de un grafo G si H puede obtenerse de un subgrafo de G contrayendo aristas. La teoría de Grafos Menores desarrollada por Robertson y Seymour en una serie de más de 20 artículos (1983-2012) es uno de los resultados modernos más impresionantes en Teoría de Grafos y Combinatoria. El objetivo de esta teoría era probar la conjetura de Wagner (afirmando que no hay una anticadena infinita con respecto a la relación menor del gráfico), pero como subproducto de la prueba, también surgieron varias aplicaciones algorítmicas. En este curso nos centraremos en los aspectos algorítmicos de la teoría de grafos menores, con especial énfasis en la noción crucial de ancho de árbol. Para describir algunas de estas aplicaciones algorítmicas, utilizaremos el marco moderno de Complejidad Parametrizada desarrollado en los años 90 por Downey y Fellows, y que se ha consolidado como una de las áreas más activas de la Teoría de Grafos Algorítmicos. En pocas palabras, el principal objetivo de la Complejidad Parametrizada es analizar la complejidad de los problemas de optimización de una forma más refinada que la clásica dicotomía “P vs NP”. Para ello, se mide la complejidad de un algoritmo no sólo en términos de su tamaño de entrada, sino también en función de un parámetro adicional que puede capturar la dificultad inherente del problema considerado.

Idioma: Español, con material en inglés

Requisitos: Conocimiento de teoría de grafos, algoritmos sobre grafos, y complejidad computacional.