Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403420" target="_blank" >RIV/00216208:11320/19:10403420 - isvavai.cz</a>

Výsledek na webu

<a href="https://drops.dagstuhl.de/opus/volltexte/2019/11484/pdf/LIPIcs-IPEC-2019-23.pdf" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2019/11484/pdf/LIPIcs-IPEC-2019-23.pdf</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.IPEC.2019.23" target="_blank" >10.4230/LIPIcs.IPEC.2019.23</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

ISBN

978-3-95977-129-0

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

11

Strana od-do

1-11

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Dagstuhl, Germany

Datum konání akce

11. 9. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—