Graph Minors:Proofs and Algorithms

The course is open to any interested person. Please confirm to mcomputing at your interest.


Nov 23, 2015 from 10:00 AM to 11:00 AM (Europe/Madrid / UTC100)


room S208, edifici Omega, Campus Nord

Add event to calendar


Speaker: Dimitrios Thilikos, University of Athens


The Graph Minors project developed by Robertson and Seymour towards proving Wagner's Conjecture, despite its deep combinatorial nature, has been characterised as one the most influential results in algorithmic graph theory. In this tutorial, we describe the basic combinatorial ideas of the proof and the main algorithmic techniques that emerged by this project. We also present some of the the most challenging open problems in this area.

Contents of the course:

Part 1. Wagner's Conjecture and the Graph Minors series

1.1. Graph Minors and W.Q.O.
1.2. Relations on Graphs
1.3. Wagner's Conjecture
1.4. Kruskal's Theorem
1.5. Branch decompositions
1.6. The grid-minor-excluding theorem
1.7. Wagner's conjecture for planar graphs

Part 2. Algorithmic consequences of the R&S theorem

2.1. Graph parameters
2.2. Parameterized complexity
2.3. Parameters, Classes and Obstructions
2.4. Meta-algorithms from Graph Minors
2.5. Applications

Part 3. Bidimensionality for minors and contractions

3.1. Win/Win approach
3.2 Minor Bidimensionality
3.3 Contraction-Bidimensionality
3.4 Limits of bidimensionality

Part 4. The irrelevant vertex technique

4.1. The k-disjoint paths problem
4.2. Walls and their subdivisions
4.3. Irrelevant vertices
4.4. More problems
4.5 Open problems


Supported by the MCINN program "ayudas de movilidad de profesores en másters oficiales"