Independent Set on P${}_k$-Free Graphs in Quasi-Polynomial Time

Abstract

We present an algorithm that takes as input a graph $G$ with weights on the vertices, and computes a maximum weight independent set $S$ of $G$. If the input graph $G$ excludes a path $P_k$ on $k$ vertices as an induced subgraph, the algorithm runs in time $n^{O(k^2{\log }^{3}n)}$. Hence, for every fixed $k$ our algorithm runs in quasi-polynomial time. This resolves in the affirmative an open problem of [Thomassé, SODA'20 invited presentation]. Previous to this work, polynomial time algorithms were only known for $P_4$-free graphs [Corneil et al., DAM'81], $P_5$-free graphs [Lokshtanov et al., SODA'14], and $P_6$-free graphs [Grzesik et al., SODA'19]. For larger values of $t$, only $2^{O(\sqrt{kn\log n})}$ time algorithms [Bascó et al., Algorithmica'19] and quasi-polynomial time approximation schemes [Chudnovsky et al., SODA'20] were known. Thus, our work is the first to offer conclusive evidence that Independent Set on $P_k$-free graphs is not NP-complete for any integer $k$. Additionally we show that for every graph $H$, if there exists a quasi-polynomial time algorithm for Independent Set on $C$-free graphs for every connected component $C$ of $H$, then there also exists a quasi-polynomial time algorithm for {\sc Independent Set} on $H$-free graphs. This lifts our quasi-polynomial time algorithm to $T_k$-free graphs, where $T_k$ has one component that is a $P_k$, and $k-1$ components isomorphic to a fork (the unique $5$-vertex tree with a degree $3$ vertex).

17 pages long. No figures. Typos fixed and constants used in measure analysis have been corrected from first version