Many computationally hard graph problems can be solved efficiently after placing appropriate restrictions on the input graphs. One reason that might explain this jump in complexity is that the class of restricted inputs has bounded “width”. There are several ways of defining a notion of “width”, giving rise for example to well-known width parameters such as tree-width and clique-width.

In the talk, I will focus on the width parameter mim-width, introduced by Vatshelle. The modelling power of mim-width is stronger than that of clique-width, in the sense that graphs of bounded clique-width have bounded mim-width but there exist graph classes with bounded mim-width and unbounded clique-width. I will overview structural properties and algorithmic applications of this parameter and present recent joint work with Nick Brettell, Jake Horsfield, Giacomo Paesani and Daniël Paulusma.

The seminar was held by Zoom. 

The slides of the talk are available in pdf at this link.