Zoom link: https://princeton.zoom.us/j/94439172371

Password required

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 Pk on  k vertices as an induced subgraph, the algorithm runs in time n^O(k^2 (log n)^3). Hence,for every fixed k our algorithm runs in quasi-polynomial time. This resolves in the affirmative an open problem of [Thomasse, 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(sqrt{t*n*log n}) time algorithms [Bacso 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 Pk-free graphs is not NP-complete for any integer k. Joint work with Peter Gartland (UCSB)