Structural Parametrizations of the Maximum Independent Set Problem

Excluding a graph (or a family of graphs) under a fixed containment relation can yield graph classes with very particular properties. Such properties can often be exploited for the design of efficient algorithms on the resulting graph classes. In this talk we survey several such structural parametrizations for the case of the Maximum Independent Set Problem, present new developments and open problems.

Everyone is welcome and encouraged to attend.