We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most clog10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasipolynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible).

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H-free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F-free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let St,t,t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G, one can in polynomial time find either an induced St,t,t in G, or a balanced separator consisting of O(log|V(G)|) vertex neighborhoods in G, or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G. This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O(log|V(G)|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

A vertex set S in a graph G is a minimal separator if there exist vertices u and v that are in distinct connected components of G — S, but in the same connected component of G — S' for every S' ⊂ S. A class F of graphs is called tame if there exists a constant c so that every graph in F on n vertices contains at most O(nc) minimal separators. If there exists a constant c so that every graph in F on n vertices contains at most O(nclog n) minimal separators the class is strongly-quasi-tame. If there exists a constant c > 1 so that F contains n-vertex graphs with at least cn minimal separators for arbitrarily large n then F is called feral. The classification of graph classes into tame or feral has numerous algorithmic consequences, and has recently received considerable attention.

A class F of graphs is called tame if every graph in F on n vertices contains at most nO(1) minimal separators, quasi-tame if every graph in F on n vertices contains at most 2logO(1)(n) minimal separators, and feral if there exists a constant c > 1 so that F contains n-vertex graphs with at least cn minimal separators for arbitrarily large n. The classification of graph classes into (quasi-) tame or feral has numerous algorithmic consequences, and has recently received considerable attention.

For an integer t, a graph G is called C>t-free if G does not contain any induced cycle on more than t vertices. We prove the following statement: for every pair of integers d and t and a statement φ, there exists an algorithm that, given an n-vertex C>t-free graph G with weights on vertices, finds in time n(log3 n) a maximum-weight vertex subset S such that G[S] has degeneracy at most d and satisfies φ. The running time can be improved to n(log2 n) assuming G is Pt-free, that is, G does not contain an induced path on t vertices. This expands the recent results of the authors [FOCS 2020 and SOSA 2021] on the Maximum Weight Independent Set problem on Pt-free graphs in two directions: by encompassing the more general setting of C>t-free graphs, and by being applicable to a much wider variety of problems, such as Maximum Weight Induced Forest or Maximum Weight Induced Planar Graph.

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 Pkon k vertices as an induced subgraph, the algorithm runs in time nO(k2log3n). 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 2O(√{knlogn})time algorithms [Bacsó et al., Algorithmica'19] and quasipolynomial 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. Additionally we show that for every graph H, if there exists a quasi-polynomial time algorithm for Independent Seton C-free graphs for every connected component C of H, then there also exists a quasi-polynomial time algorithm for Independent Set on H-free graphs. This lifts our quasi-polynomial time algorithm to Tk-free graphs, where Tkhas one component that is a Pk, and k-1 components isomorphic to a fork (the unique 5-vertex tree with a degree 3 vertex).