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

W pracy rozważamy problem znajdowania największego podgrafu o ograniczonej degeneracji, spełniającego zadaną formułę CMSO2. Pokazujemy, że problem ten da się rozwiązać w czasu quasiwielomianowym w klasie grafów bez indukowanych cykli długości większej niż t.[CR][LF]Implikuje to quasiwielomianowe algorytmy dla klasycznych problemów, w tym największego zbioru niezależnego czy najmniejszego zbioru przecinającego wszystkie cykle.

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.