# Block Elimination Distance

No Thumbnail Available

## Date

2021

## Journal Title

## Journal ISSN

## Volume Title

## Publisher

Springer international Publishing Ag

## Open Access Color

## OpenAIRE Downloads

## OpenAIRE Views

## 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 is an element of 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 NPcomplete. 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 is an element of 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 boolean AND G((k)), for every k is an element of N and every non-trivial minor-closed graph class G.

## Description

Diner, Oznur Yasar/0000-0002-9271-2691; Stamoulis, Giannos/0000-0002-4175-7793

## Keywords

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

## Turkish CoHE Thesis Center URL

## Fields of Science

## Citation

0

## WoS Q

N/A

## Scopus Q

N/A

## Source

47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) -- JUN 23-25, 2021 -- Warsaw, POLAND

## Volume

12911

## Issue

## Start Page

28

## End Page

38