Abstract: 

Structural graph theory has played a central role in the design of efficient algorithms for hard optimization problems. At the core of this approach lies the notion of treewidth, which measures how close a graph is to a tree, together with the fact that large treewidth forces the presence of large grid minors. Many algorithmic ideas in this field can then be viewed as ways of understanding, exploiting, or controlling this large grid structure. In this talk, we will discuss two research directions that follow this philosophy.

In the first part, we will focus on approximation and parameterized algorithms in sparse and geometric graph classes. Starting from Baker’s technique for planar graphs, we will explain how large grid structure can be controlled through deletion or contraction decompositions, leading to efficient algorithms.

In the second part, we will turn to disjoint paths problems. The classical Robertson–Seymour algorithm for disjoint paths was one of the first major demonstrations of how grid minors and irrelevant vertices can be used algorithmically. We will discuss variants with length constraints, explain why the usual arguments become much less effective in that setting, and present some possible directions for overcoming this difficulty.