# Block Elimination Distance

Loading...

## Files

## Date

2022

## Authors

Diner, Oznur Yasar

Giannopoulou, Archontia C.

Stamoulis, Giannos

Thilikos, Dimitrios M.

## Journal Title

## Journal ISSN

## Volume Title

## Publisher

Springer Japan Kk

## 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))) ) N We show that, for every nontrivial hereditary class g, the problem of deciding whether G is an element of 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 ofk 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. 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.Please check and confirm if the authors Given and Family names have been correctly identified for author znur YaYar Diner. All authors names have been identified conectly. Please confirm if the corresponding author is correctly identified. Amend if necessary.This is correct

## Description

## Keywords

Graph minors, Block elimination distance, Elimination distance, Minor obstructions, Parameterized algorithms

## Turkish CoHE Thesis Center URL

## Fields of Science

## Citation

1

## WoS Q

N/A

## Scopus Q

Q2

## Source

Graphs and Combinatorics

## Volume

38

## Issue

5