On the Path to Independence

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

Time: 14:30 -- Location: LIX

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 fixed graph H as an induced subgraph (so-called H-free graphs) is not yet settled. While Independent Set is still NP-hard for H-free graphs for most fixed graphs H, the complexity is open when H is a path of 6 or more vertices (it is polynomial when H is a shorter path).

In this talk, I will survey the known results about Independent Set on H-free graphs. In particular, I will speak about recent work with Daniel Lokshtanov and Marcin Pilipczuk (http://arxiv.org/abs/1507.02163 [1], to appear in SODA 2016), where we show that when H is a path on 6 vertices, Independent Set has a quasipolynomial-time algorithm. Hence, in this case, a simultaneous NP-hardness result would imply quasipolynomial-time algorithms for all problems in NP.

Category: seminars
Tags: Plateau seminar