FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More

Bart M.P. Jansen; Jari J.H. de Kroon

doi:10.1007/978-3-030-86838-3_6

FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More

Bart M.P. Jansen, Jari J.H. de Kroon (Corresponding author)

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

8 Citations (Scopus)

Abstract

For a hereditary graph class H, the H -elimination distance of a graph G is the minimum number of rounds needed to reduce G to a member of H by removing one vertex from each connected component in each round. The H -treewidth of a graph G is the minimum, taken over all vertex sets X for which each connected component of G- X belongs to H, of the treewidth of the graph obtained from G by replacing the neighborhood of each component of G- X by a clique and then removing V(G) \ X. These parameterizations recently attracted interest because they are simultaneously smaller than the graph-complexity measures treedepth and treewidth, respectively, and the vertex-deletion distance to H. For the class H of bipartite graphs, we present non-uniform fixed-parameter tractable algorithms for testing whether the H -elimination distance or H -treewidth of a graph is at most k. Along the way, we also provide such algorithms for all graph classes H defined by a finite set of forbidden induced subgraphs.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers
Editors	Łukasz Kowalik, Michał Pilipczuk, Paweł Rzążewski
Place of Publication	Cham
Publisher	Springer
Pages	80-93
Number of pages	14
ISBN (Electronic)	978-3-030-86838-3
ISBN (Print)	978-3-030-86837-6
DOIs	https://doi.org/10.1007/978-3-030-86838-3_6
Publication status	Published - 20 Sept 2021
Event	47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online Duration: 23 Jun 2021 → 25 Jun 2021

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	12911
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Theoretical Computer Science and General Issues (LNTCS)
Volume	12911
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Conference

Conference	47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
City	Virtual, Online
Period	23/06/21 → 25/06/21

Bibliographical note

Funding Information:
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch).

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch).

Keywords

Elimination distance
FPT
Odd cycle transversal

Access to Document

10.1007/978-3-030-86838-3_6

pdfFinal published version, 360 KBLicence: CC BY

Cite this

Jansen, B. M. P., & de Kroon, J. J. H. (2021). FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More. In Ł. Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (pp. 80-93). (Lecture Notes in Computer Science (LNCS); Vol. 12911), (Theoretical Computer Science and General Issues (LNTCS); Vol. 12911). Springer. https://doi.org/10.1007/978-3-030-86838-3_6

Jansen, Bart M.P. ; de Kroon, Jari J.H. / FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More. Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers. editor / Łukasz Kowalik ; Michał Pilipczuk ; Paweł Rzążewski. Cham : Springer, 2021. pp. 80-93 (Lecture Notes in Computer Science (LNCS)). (Theoretical Computer Science and General Issues (LNTCS)).

@inproceedings{b42a41ae4d2c4e7e8cd9bde813948b46,

title = "FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More",

abstract = "For a hereditary graph class H, the H -elimination distance of a graph G is the minimum number of rounds needed to reduce G to a member of H by removing one vertex from each connected component in each round. The H -treewidth of a graph G is the minimum, taken over all vertex sets X for which each connected component of G- X belongs to H, of the treewidth of the graph obtained from G by replacing the neighborhood of each component of G- X by a clique and then removing V(G) \textbackslash{} X. These parameterizations recently attracted interest because they are simultaneously smaller than the graph-complexity measures treedepth and treewidth, respectively, and the vertex-deletion distance to H. For the class H of bipartite graphs, we present non-uniform fixed-parameter tractable algorithms for testing whether the H -elimination distance or H -treewidth of a graph is at most k. Along the way, we also provide such algorithms for all graph classes H defined by a finite set of forbidden induced subgraphs.",

keywords = "Elimination distance, FPT, Odd cycle transversal",

author = "Jansen, \{Bart M.P.\} and \{de Kroon\}, \{Jari J.H.\}",

note = "Funding Information: This project has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch). Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 ; Conference date: 23-06-2021 Through 25-06-2021",

year = "2021",

month = sep,

day = "20",

doi = "10.1007/978-3-030-86838-3\_6",

language = "English",

isbn = "978-3-030-86837-6",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "80--93",

editor = "{\L}ukasz Kowalik and Micha{\l} Pilipczuk and Pawe{\l} Rz{\c a}{\.z}ewski",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

}

Jansen, BMP & de Kroon, JJH 2021, FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More. in Ł Kowalik, M Pilipczuk & P Rzążewski (eds), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers. Lecture Notes in Computer Science (LNCS), vol. 12911, Theoretical Computer Science and General Issues (LNTCS), vol. 12911, Springer, Cham, pp. 80-93, 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021, Virtual, Online, 23/06/21. https://doi.org/10.1007/978-3-030-86838-3_6

FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More. / Jansen, Bart M.P.; de Kroon, Jari J.H. (Corresponding author).
Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers. ed. / Łukasz Kowalik; Michał Pilipczuk; Paweł Rzążewski. Cham: Springer, 2021. p. 80-93 (Lecture Notes in Computer Science (LNCS); Vol. 12911), (Theoretical Computer Science and General Issues (LNTCS); Vol. 12911).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More

AU - Jansen, Bart M.P.

AU - de Kroon, Jari J.H.

N1 - Funding Information: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch). Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/9/20

Y1 - 2021/9/20

N2 - For a hereditary graph class H, the H -elimination distance of a graph G is the minimum number of rounds needed to reduce G to a member of H by removing one vertex from each connected component in each round. The H -treewidth of a graph G is the minimum, taken over all vertex sets X for which each connected component of G- X belongs to H, of the treewidth of the graph obtained from G by replacing the neighborhood of each component of G- X by a clique and then removing V(G) \ X. These parameterizations recently attracted interest because they are simultaneously smaller than the graph-complexity measures treedepth and treewidth, respectively, and the vertex-deletion distance to H. For the class H of bipartite graphs, we present non-uniform fixed-parameter tractable algorithms for testing whether the H -elimination distance or H -treewidth of a graph is at most k. Along the way, we also provide such algorithms for all graph classes H defined by a finite set of forbidden induced subgraphs.

AB - For a hereditary graph class H, the H -elimination distance of a graph G is the minimum number of rounds needed to reduce G to a member of H by removing one vertex from each connected component in each round. The H -treewidth of a graph G is the minimum, taken over all vertex sets X for which each connected component of G- X belongs to H, of the treewidth of the graph obtained from G by replacing the neighborhood of each component of G- X by a clique and then removing V(G) \ X. These parameterizations recently attracted interest because they are simultaneously smaller than the graph-complexity measures treedepth and treewidth, respectively, and the vertex-deletion distance to H. For the class H of bipartite graphs, we present non-uniform fixed-parameter tractable algorithms for testing whether the H -elimination distance or H -treewidth of a graph is at most k. Along the way, we also provide such algorithms for all graph classes H defined by a finite set of forbidden induced subgraphs.

KW - Elimination distance

KW - FPT

KW - Odd cycle transversal

UR - https://www.scopus.com/pages/publications/85115854878

U2 - 10.1007/978-3-030-86838-3_6

DO - 10.1007/978-3-030-86838-3_6

M3 - Conference contribution

AN - SCOPUS:85115854878

SN - 978-3-030-86837-6

T3 - Lecture Notes in Computer Science (LNCS)

SP - 80

EP - 93

BT - Graph-Theoretic Concepts in Computer Science

A2 - Kowalik, Łukasz

A2 - Pilipczuk, Michał

A2 - Rzążewski, Paweł

PB - Springer

CY - Cham

T2 - 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021

Y2 - 23 June 2021 through 25 June 2021

ER -

Jansen BMP, de Kroon JJH. FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More. In Kowalik Ł, Pilipczuk M, Rzążewski P, editors, Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers. Cham: Springer. 2021. p. 80-93. (Lecture Notes in Computer Science (LNCS)). (Theoretical Computer Science and General Issues (LNTCS)). doi: 10.1007/978-3-030-86838-3_6

FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this