Articles by Erik Jan van Leeuwen

On the Path to Independence

-- 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 ...