Subexponential-Time Algorithms for Maximum Independent Set in Pt-Free and Broom-Free Graphs

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on P-t-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t = 1, there is an algorithm for Maximum Independent Set on P-t-free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in 2(O(root tn log n)) time on P-t-free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. Scattered Set is the generalization of Maximum Independent Set where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges)