Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs
Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Źsolt Tuza, Erik Jan van Leeuwen · Algorithmica · 2018
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\le 5$$ (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014, pp 570–581, 2014), and an algorithm for $$t=6$$ announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on $${P}_6$$ -free graphs. CoRR, arXiv:1707.05491 , 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any $$t\ge 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^{\mathcal {O}(\sqrt{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):