Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Jana Novotná; Karolina Okrasa; Michal Pilipczuk; Pawel Rzazewski; Erik Jan van Leeuwen; Bartosz Walczak

doi:10.1007/s00453-020-00745-z

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

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⁽ⁿ⁾ 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; andthe 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 2O~(n2/3) time, for every fixed t; anda largest induced planar graph in a string graph can be found in 2O~(n2/3) time.

Original language	English
Pages (from-to)	2634-2650
Number of pages	17
Journal	Algorithmica
Volume	83
DOIs	https://doi.org/10.1007/s00453-020-00745-z
Publication status	Published - Aug 2021

Bibliographical note

Funding Information:
The results presented in this paper were obtained during the Parameterized Algorithms Retreat of the algorithms group of the University of Warsaw (PARUW), held in Karpacz in February 2019. This Retreat was financed by the project CUTACOMBS, which has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 714704). We are grateful to the anonymous reviewer at IPEC 2019 for suggesting the generalization of the algorithm described in Sect. .

Funding Information:
The extended abstract of this paper was presented on IPEC 2019 []. J.N. was supported by student Grants GAUK 1277018, SVV-2017-260452. M.P. was suppored by the Project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 677651). P.Rz. was supported by Polish National Science Centre Grant No. 2018/31/D/ST6/00062. B.W. was partially supported by Polish National Science Centre Grant No. 2015/17/B/ST6/01873.

Publisher Copyright:
© 2020, The Author(s).

Keywords

Feedback vertex set
P -free graphs
String graphs
Subexponential algorithm

Access to Document

10.1007/s00453-020-00745-zLicence: CC BY

Novotná2021_Article_Subexponential-TimeAlgorithmsFFinal published version, 2.23 MBLicence: CC BY

Cite this

@article{6539230f8096477ea0600065d22c887f,

title = "Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.",

abstract = "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; andthe 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 Pt-free graph can be found in 2O~(n2/3) time, for every fixed t; anda largest induced planar graph in a string graph can be found in 2O~(n2/3) time.",

keywords = "Feedback vertex set, P -free graphs, String graphs, Subexponential algorithm",

author = "Jana Novotn{\'a} and Karolina Okrasa and Michal Pilipczuk and Pawel Rzazewski and Leeuwen, {Erik Jan van} and Bartosz Walczak",

note = "Funding Information: The results presented in this paper were obtained during the Parameterized Algorithms Retreat of the algorithms group of the University of Warsaw (PARUW), held in Karpacz in February 2019. This Retreat was financed by the project CUTACOMBS, which has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (Grant Agreement No. 714704). We are grateful to the anonymous reviewer at IPEC 2019 for suggesting the generalization of the algorithm described in Sect. . Funding Information: The extended abstract of this paper was presented on IPEC 2019 []. J.N. was supported by student Grants GAUK 1277018, SVV-2017-260452. M.P. was suppored by the Project TOTAL that has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (Grant Agreement No. 677651). P.Rz. was supported by Polish National Science Centre Grant No. 2018/31/D/ST6/00062. B.W. was partially supported by Polish National Science Centre Grant No. 2015/17/B/ST6/01873. Publisher Copyright: {\textcopyright} 2020, The Author(s).",

year = "2021",

month = aug,

doi = "10.1007/s00453-020-00745-z",

language = "English",

volume = "83",

pages = "2634--2650",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

}

TY - JOUR

T1 - Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

AU - Novotná, Jana

AU - Okrasa, Karolina

AU - Pilipczuk, Michal

AU - Rzazewski, Pawel

AU - Leeuwen, Erik Jan van

AU - Walczak, Bartosz

N1 - Funding Information: The results presented in this paper were obtained during the Parameterized Algorithms Retreat of the algorithms group of the University of Warsaw (PARUW), held in Karpacz in February 2019. This Retreat was financed by the project CUTACOMBS, which has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 714704). We are grateful to the anonymous reviewer at IPEC 2019 for suggesting the generalization of the algorithm described in Sect. . Funding Information: The extended abstract of this paper was presented on IPEC 2019 []. J.N. was supported by student Grants GAUK 1277018, SVV-2017-260452. M.P. was suppored by the Project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 677651). P.Rz. was supported by Polish National Science Centre Grant No. 2018/31/D/ST6/00062. B.W. was partially supported by Polish National Science Centre Grant No. 2015/17/B/ST6/01873. Publisher Copyright: © 2020, The Author(s).

PY - 2021/8

Y1 - 2021/8

N2 - 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; andthe 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 Pt-free graph can be found in 2O~(n2/3) time, for every fixed t; anda largest induced planar graph in a string graph can be found in 2O~(n2/3) time.

AB - 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; andthe 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 Pt-free graph can be found in 2O~(n2/3) time, for every fixed t; anda largest induced planar graph in a string graph can be found in 2O~(n2/3) time.

KW - Feedback vertex set

KW - P -free graphs

KW - String graphs

KW - Subexponential algorithm

UR - http://www.scopus.com/inward/record.url?scp=85088961027&partnerID=8YFLogxK

U2 - 10.1007/s00453-020-00745-z

DO - 10.1007/s00453-020-00745-z

M3 - Article

C2 - 34720297

SN - 0178-4617

VL - 83

SP - 2634

EP - 2650

JO - Algorithmica

JF - Algorithmica

ER -

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this