TY - JOUR
T1 - Block Elimination Distance
AU - Diner, Öznur Yaşar
AU - Giannopoulou, Archontia C.
AU - Stamoulis, Giannos
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.
PY - 2022/10
Y1 - 2022/10
N2 - 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))). 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. 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 YaŸar Diner.All authors names have been identified correctly.Please confirm if the corresponding author is correctly identified. Amend if necessary.This
AB - 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))). 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. 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 YaŸar Diner.All authors names have been identified correctly.Please confirm if the corresponding author is correctly identified. Amend if necessary.This
KW - Block elimination distance
KW - Elimination distance
KW - Graph minors
KW - Minor obstructions
KW - Parameterized algorithms
UR - http://www.scopus.com/inward/record.url?scp=85135460318&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85135460318&partnerID=8YFLogxK
U2 - 10.1007/s00373-022-02513-y
DO - 10.1007/s00373-022-02513-y
M3 - Article
AN - SCOPUS:85135460318
SN - 0911-0119
VL - 38
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 5
M1 - 133
ER -