Independent Set in P5-Free Graphs in Polynomial Time

The Independent Set problem is NP-hard in general, however polynomial time algorithms exist for the problem on various specific graph classes. Over the last couple of decades there has been a long sequence of papers exploring the boundary between the NP-hard and polynomial time solvable cases. In particular the complexity of Independent Set on P5-free graphs has received significant attention, and there has been a long list of results showing that the problem becomes polynomial time solvable on subclasses of P5-free graphs. In this paper we give the first polynomial time algorithm for Independent Set on P5-free graphs. Our algorithm also works for the Weighted Independent Set problem