Independent Set on P5-free graphs, an empirical study

Abstract

We implement the recent polynomial time algorithm for the independent set problem on P5-free graphs, and study the performance of this algorithm on graphs of size up to 50. Our empirical results show that the algorithm is probably much faster than its theoretical running-time upperbound.