Block Elimination Distance

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Revised Selected Papers
EditorsLukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages11
ISBN (Print)9783030868376
StatePublished - 2021
Event47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online
Duration: Jun 23 2021Jun 25 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12911 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
CityVirtual, Online


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Block Elimination Distance'. Together they form a unique fingerprint.

Cite this