Courcelle’s theorem, which states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth, is one of the most celebrated results in parameterized complexity, because it implies the existence of linear-time FPT algorithms for a host of NP-hard problems. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula.
In this talk we take a high-level view of this area of research and survey results that attempt to improve upon this performance by considering more restricted classes of inputs. This is known to be impossible, even if we restrict the input to graphs of treewidth 1 (trees) and only consider FO logic; or if we consider graphs of pathwidth 1 (caterpillars) and consider MSO logic. This would seem to indicate that Courcelle’s theorem is « best possible ». Surprisingly, we discover that in the only remaining case which has so far been overlooked, namely FO logic on graphs of constant pathwidth, all known hardness results fail, because the problem becomes tractable with an elementary parameter dependence on the input formula. Our result generalizes previously known meta-theorems for the much more restricted parameter tree-depth.
Results based on a preprint found here: https://arxiv.org/abs/2210.09899
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne