On maximum independent sets in P5P5-free graphs

The complexity status of the Maximum Independent Set Problem (MIS) for the family of P5P5-free graphs is unknown. Although for many subclasses of P5P5-free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general graphs are known so far. In this note we present the first algorithm to solve MIS for P5P5-free graphs in subexponential time.