Subexponential-time algorithms for finding large induced sparse subgraphs
share
Let C and D be hereditary graph classes. Consider the following problem: given a graph G∈D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2^o(n) time, where n is the number of vertices of G, if the following conditions are satisfied: * the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; * the graphs in D admit balanced separators of size governed by their density, e.g., O(Δ) or O(√(m)), where Δ and m denote the maximum degree and the number of edges, respectively; and * the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D: * a largest induced forest in a P_t-free graph can be found in 2^Õ(n^2/3) time, for every fixed t; and * a largest induced planar graph in a string graph can be found in 2^Õ(n^3/4) time.
READ FULL TEXT