Corelab Seminar

Michael Lampis
Grundy distinguishes treewidth from pathwidth

In this talk we are interested in the "price of generality" associated with the transition from pathwidth to treewidth. Treewidth and pathwidth are two of the most studied notions in parameterized complexity, where they are used to provide fixed-parameter tractable algorithms for a large variety of NP-hard problems. Because treewidth generalizes pathwidth, some problems which are tractable for pathwidth should become intractable for treewidth (this is the "price" of the added generality of treewidth). Which are these problems?
So far, the same question has been posed for many other pairs of prominent structural parameters, such as treewidth vs. clique-width, pathwidth vs. tree-depth, and tree-depth vs. vertex cover. For each such pair, several natural problems are known which give examples of this complexity transition. The only exception is, to the best of our knowledge, the transition from pathwidth to treewidth, where essentially all known problems seem to have the same complexity for both parameters. Our main goal in this talk is to give the first natural example of a problem that is FPT parameterized by pathwidth but W[1]-hard parameterized by treewidth. This problem is Grundy Coloring, the problem of ordering the vertices of a graph in a way that maximizes the number of colors used by the greedy First-Fit Coloring heuristic.

Joint work with Rémy Belmonte, Eun Jung Kim, Valia Mitsou, and Yota Otachi, in ESA 2020. Full version available at