Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time

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 CMSO 2 statement ϕ, there exists an algorithm that, given an n-vertex C >t -free graph G with weights on vertices, finds in time n O(log 3 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 O(log 2 n) assuming G is P t -free, that is, G does not contain an induced path on t vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the Maximum Weight Independent Set problem on P t -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.