## Abstract

We introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class G, the class B(G) contains all graphs whose blocks belong to G and the class A(G) contains all graphs where the removal of a vertex creates a graph in G. Given a hereditary graph class G, we recursively define G^{(} ^{k} ^{)} so that G^{(0 )}= B(G) and, if k≥ 1, G^{(} ^{k} ^{)}= B(A(G^{(} ^{k} ^{-} ^{1} ^{)}) ). The block elimination distance of a graph G to a graph class G is the minimum k such that G∈ G^{(} ^{k} ^{)} and can be seen as an analog of the elimination distance parameter, defined in [J. Bulian & A. Dawar. Algorithmica, 75(2):363–382, 2016], with the difference that connectivity is now replaced by biconnectivity. We show that, for every non-trivial hereditary class G, the problem of deciding whether G∈ G^{(} ^{k} ^{)} is NP-complete. We focus on the case where G is minor-closed and we study the minor obstruction set of G^{(} ^{k} ^{)} i.e., the minor-minimal graphs not in G^{(} ^{k} ^{)}. We prove that the size of the obstructions of G^{(} ^{k} ^{)} is upper bounded by some explicit function of k and the maximum size of a minor obstruction of G. This implies that the problem of deciding whether G∈ G^{(} ^{k} ^{)} is constructively fixed parameter tractable, when parameterized by k. Our results are based on a structural characterization of the obstructions of B(G), relatively to the obstructions of G. Finally, we give two graph operations that generate members of G^{(} ^{k} ^{)} from members of G^{(} ^{k} ^{-} ^{1} ^{)} and we prove that this set of operations is complete for the class O of outerplanar graphs. This yields the identification of all members O∩ G^{(} ^{k} ^{)}, for every k∈ N and every non-trivial minor-closed graph class G.

Original language | English (US) |
---|---|

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 Science and Business Media Deutschland GmbH |

Pages | 28-38 |

Number of pages | 11 |

ISBN (Print) | 9783030868376 |

DOIs | |

State | Published - 2021 |

Event | 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online Duration: Jun 23 2021 → Jun 25 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 | 6/23/21 → 6/25/21 |

## Keywords

- Biconnected graphs
- Elimination distance
- Graph minors
- Obstructions
- Parameterized algorithms

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science