Independent Set on $\mathrm{P}_{k}$-Free Graphs in Quasi-Polynomial Time

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 P4-free graphs [Corneil et al., DAM'81], P5-free graphs [Lokshtanov et al., SODA'14], and P6-free graphs [Grzesik et al., SODA'19]. For larger values of t, only 2 O( √ 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 quasipolynomial time algorithm for 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).