Michail Lampis: The Landscape of Structural Graph Parameters

In traditional computational complexity we measure algorithm running times as functions of one variable, the size of the input. Though in this setting our goal is usually to design polynomial-time algorithms, most interesting graph problems are unfortunately believed to require exponential time to solve exactly.

Parameterized complexity theory refines this by introducing a second variable, called the parameter, which is supposed to quantify the “hardness” of each specific instance. The goal now becomes to confine the combinatorial explosion to the parameter, by designing an algorithm that runs in time polynomial in the size of the input, though inevitably exponential in the parameter. This will allow us to tackle instances where the parameter value is much more modest than the input size, which will happen often if the parameter is chosen well.

Of course, this setting is rather general and there are countless ways in which one may attempt to measure the hardness of specific instances, depending on the problem. The parameterized graph algorithms literature has been dominated for a long time by a very successful notion called treewidth, which measures graph complexity by quantifying a graph's similarity to a tree. However, more recently the study of alternative graph parameters and widths has become more popular. In this (self-contained) talk we will attempt to explore the algorithmic properties of treewidth, its related graph width parameters, as well as other graph invariants which may serve as measurements of a graph's complexity such as Vertex Cover, or Max-Leaf number. We will focus especially on general results which prove tractability for whole classes of problems characterized by expressibility in certain logics, results often referred to as "algorithmic meta-theorems".