Quasi-polynomial-time algorithm for Independent Set in $P_t$-free graphs via shrinking the space of induced paths

Abstract

In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in $P_t$-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm runs in time $n^{\mathcal{O}({\log }^{3}n)}$, where $t$ is assumed to be a constant. Inspired by their ideas, we present an arguably simpler algorithm with an improved running time bound of $n^{\mathcal{O}({\log }^{2}n)}$. Our main insight is that a connected $P_t$-free graph always contains a vertex $w$ whose neighborhood intersects, for a constant fraction of pairs $\{u,v\}\in \left(\genfrac{}{}{0ex}{}{V(G)}{2}\right)$, a constant fraction of induced $u-v$ paths. Since a $P_t$-free graph contains $\mathcal{O}(n^{t-1})$ induced paths in total, branching on such a vertex and recursing independently on the connected components leads to a quasi-polynomial running time bound. We also show that the same approach can be used to obtain quasi-polynomial-time algorithms for related problems, including Maximum Weight Induced Matching and 3-Coloring.

Paper accepted to SOSA 2021. The results on $C_{>t}$-free graphs from v1 were moved to arXiv:2007.11402