H-free graphs are graphs without a fixed graph H as an induced subgraph. It is known that Independent Set is NP-hard if H is *not* a path or a subdivision of K1,3. It is unknown whether Independent Set becomes NP-hard on H-free graphs if H is a (very long) path. However, we do know that the problem is polynomial-time solvable when H is a path on at most 5 vertices. In this talk, we show that Independent Set can be solved in quasipolynomial time if H is a path on 6 vertices.
This talk is based on joint work with Daniel Lokshtanov and Marcin Pilipczuk, and will appear in SODA 2016.