Block Elimination Distance
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? 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. © 2021, Springer Nature Switzerland AG.
Volume
12911 LNCSCollections
Related items
Showing items related by title, author, creator and subject.
-
The multicolored graph realization problem
Díaz, J.; Diner, Ö.Y.; Serna, M.; Serra, O. (Elsevier B.V., 2022)We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G,?), i.e., a graph G together with a coloring ? on its vertices. We associate each colored graph (G,?) with a ... -
Contraction and deletion blockers for perfect graphs and H-free graphs
Diner, Öznur Yaşar; Paulusma, Daniel; Picouleau, Christophe; Ries, Bernard (Elsevier Science, 2018)We study the following problem: for given integers d k and graph G can we reduce some fixed graph parameter pi of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic ... -
Orthogonal projection and liftings of Hamilton-decomposable Cayley graphs on abelian groups
Alspach, Brian; Çalışkan, Cafer; Kreher, Donald L. (Elsevier Science Bv, 2013)In this article we introduce the concept of (p alpha)-switching trees and use it to provide sufficient conditions on the abelian groups G and H for when CAY (G x H