2026-07-26T04:50:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11484 2024-03-06T10:48:08Z ddc:004 open_access

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs Novotná, Jana Okrasa, Karolina Pilipczuk, Michał Rzążewski, Paweł van Leeuwen, Erik Jan Walczak, Bartosz subexponential algorithm feedback vertex set P_t-free graphs string graphs Let C and D be hereditary graph classes. Consider the following problem: given a graph G in 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(Delta) or O(sqrt{m}), where Delta 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^{O~(n^{2/3})} time, for every fixed t; and - a largest induced planar graph in a string graph can be found in 2^{O~(n^{3/4})} time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jana Novotná and Karolina Okrasa and Michał Pilipczuk and Paweł Rzążewski and Erik Jan van Leeuwen and Bartosz Walczak 2019 Is Part Of LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2019.23 urn:nbn:de:0030-drops-114845 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.23 eng https://creativecommons.org/licenses/by/3.0/legalcode