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

2020/07/21 by Gartland, Peter, Lokshtanov, Daniel, Pilipczuk, Marcin +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2007.11402

Abstract

For an integer t, a graph G is called \emC_>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₂ statement~ϕ, there exists an algorithm that, given an n-vertex C_>t-free graph G with weights on vertices, finds in time n^{O(log4 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(log2 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 \scMaximum 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 \scMaximum Weight Induced Forest or \scMaximum Weight Induced Planar Graph.

Cited by

• Constricting the Computational Complexity Gap of the 4-Coloring Problem in (P_t,C₃)-free Graphs

Related

• Sparse induced subgraphs in P₇-free graphs of bounded clique number
• Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths
• Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
• Sparse induced subgraphs in P₆-free graphs
• Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument