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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers
EditorsLukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
PublisherSpringer
Pages80-93
Number of pages14
ISBN (Print)9783030868376
DOIs
Publication statusPublished - 2021
Event47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online
Duration: 23 Jun 202125 Jun 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12911 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
CityVirtual, Online
Period23/06/2125/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.

Keywords

  • Elimination distance
  • FPT
  • Odd cycle transversal

Fingerprint

Dive into the research topics of 'FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More'. Together they form a unique fingerprint.

Cite this