--
Erik Jan van Leeuwen
(Max-Planck Institut für Informatik, Saarbrücken, Germany)

The Independent Set problem is a fundamental and well-studied graph problem, and asks to find a largest set of pairwise nonadjacent vertices of a graph. Although Independent Set is known to be NP-hard or worse for many graph classes, surprisingly, the complexity of Independent Set on graphs that exclude a ...