Profesor(es)
Ignasi Sau Valls
Turno
Turno Tarde (13:30 a 16:30)
Cupo
120
Idioma
Español, slides en inglés.
Descripción

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.

Programa del curso

Introducción a graph minors: definiciones básicas, e ideas de la prueba del Graph Minors Theorem de Robertson y Seymour.Treewidth: definición, propiedades básicas, ejemplos de programación dinámica sobre descomoposiciones, teorema de Coucelle. Introducción a la Complejidad Parametrizada. Bidimensionalidad: ideas principales y ejemplos.
Técnicas algorítmicas avanzadas: Flat Wall Theorem, técnica “irrelevant vertex”, branching, compresión iterativa. Aplicación a problemas de modificación de grafos.

Requisitos del curso

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

Bibliografía

László Lovász. Graph Minor Theory. Bulletin of the American Mathematical Society, Volume 43, Number 1, Pgs 75-86, (2005).

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, , Michal Pilipczuk, y Saket Saurabh. Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555.

Neil Robertson, Paul D. Seymour. Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B 63(1): 65-110, 1995.

Neil Robertson, Paul D. Seymour. Graph Minors. XX. Wagner's conjecture. Journal of Combinatorial Theory, Series B 92(2): 325-357, 2004.