Block Elimination Distance Article - Octobre 2022

Öznur Yaşar Diner, Archontia Giannopoulou, Giannos Stamoulis, Dimitrios M. Thilikos

Öznur Yaşar Diner, Archontia Giannopoulou, Giannos Stamoulis, Dimitrios M. Thilikos, « Block Elimination Distance  », Graphs and Combinatorics, octobre 2022, #133. ISSN 0911-0119

Abstract

We introduce the parameter of \sl block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class $\cal G$, the class $\cal B(\cal G)$ contains all graphs whose blocks belong to $\cal G$ and the class $\cal A(\cal G)$ contains all graphs where the removal of a vertex creates a graph in $\cal G$. Given a hereditary graph class $\cal G$, we recursively define $\cal G^(k)$ so that $\cal G^(0)=\cal B(\cal G)$ and, if $k\geq 1$, $\cal G^(k)=\cal B(\cal A(\cal G^(k-1)))$. We show that, for every non-trivial hereditary class $\cal G$, the problem of deciding whether $G\in\cal G^(k)$ is \sf NP-complete. We focus on the case where $\cal G$ is minor-closed and we study the minor obstruction set of $\cal G^(k)$ i.e., the minor-minimal graphs not in $\cal G^(k)$. We prove that the size of the obstructions of $\cal G^(k)$ is upper bounded by some explicit function of $k$ and the maximum size of a minor obstruction of $\cal G$. This implies that the problem of deciding whether $G\in\cal G^(k)$ is \sl constructively fixed parameter tractable, when parameterized by $k$. Finally, we give two graph operations that generate members of $\cal G^(k)$ from members of $\cal G^(k-1)$ and we prove that this set of operations is complete for the class $\cal O$ of outerplanar graphs.

Voir la notice complète sur HAL

Actualités