## 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 - 47th International Workshop, WG 2021, Revised Selected Papers |

Editors | Lukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski |

Publisher | Springer |

Pages | 80-93 |

Number of pages | 14 |

ISBN (Print) | 9783030868376 |

DOIs | |

Publication status | Published - 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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 12911 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### 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.

## Keywords

- Elimination distance
- FPT
- Odd cycle transversal