Maria Chudnovsky, Induced minors and treewidth

This talk deals with induced minor obstructions to treewidth. The natural setup for this problem is to consider the class of graphs excluding some planar graph, and some complete bipartite graph as induced minors, and some complete graph as a subgraph. Unfortunately, such  classes still contain graphs of arbitrarily large treewidth. Moreover, a result of Alecu, Bonnet, Bureo Villafana and Trotignon and its extensions suggest that there is no elegant characterization of families of bounded treewidth in terms of induced obstructions.

On the other hand, it is conjectured that graphs in the classes as above have treewidth bounded by a poly-logarithmic function of their number of vertices. If true, this will imply the existence of quasi-polynomial time algorithms for a host of problems on such  classes that are NP-complete in the general setting.

While this conjecture remains open, in joint work with Julien Codsi, David Fischer and Daniel Lokshtanov, we were able to prove the existence of a sub-polynomial bound on treewidth in terms of the number of vertices. This in turn leads to sub-exponential algorithmic behavior.

In this talk we will discuss some ideas of the proof, and, if time permits, some results in the more general setting when the bound on the clique size is removed.