Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time

Abstract

For an integer $t$, a graph $G$ is called {\em{$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~$\varphi$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O({\log }^{4}n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $\varphi$. 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 {\sc{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 {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}.

49 pages, 2 figures. Major changes from first (preliminary) version including changing title, adding co-authors, and significant addition to content of the paper