Discrete mathematics

Independent set

Time complexity

Set (abstract data type)

Computer science

Maximal independent set

Graph

Mathematics

Combinatorics

1-planar graph

Programming language

Chordal graph

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

Independent set in P5-free graphs in polynomial time