Block Elimination Distance

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 \(\mathcal{G}\), the class \(\mathcal{B}(\mathcal{G})\) contains all graphs whose blocks belong to \(\mathcal{G}\) and the class \(\mathcal{A}(\mathcal{G})\) contains all graphs where the removal of a vertex creates a graph in \(\mathcal{G}\). Given a hereditary graph class \(\mathcal{G}\), we recursively define \(\mathcal{G}^{(k)}\) so that \(\mathcal{G}^{(0)}=\mathcal{B}(\mathcal{G})\) and, if \(k\ge 1\), \(\mathcal{G}^{(k)}=\mathcal{B}(\mathcal{A}(\mathcal{G}^{(k-1)}))\). The block elimination distance of a graph G to a graph class \(\mathcal{G}\) is the minimum k such that \(G\in \mathcal{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 \(\mathcal{G}\), the problem of deciding whether \(G\in \mathcal{G}^{(k)}\) is NP-complete. We focus on the case where \(\mathcal{G}\) is minor-closed and we study the minor obstruction set of \(\mathcal{G}^{(k)}\) i.e., the minor-minimal graphs not in \(\mathcal{G}^{(k)}\). We prove that the size of the obstructions of \(\mathcal{G}^{(k)}\) is upper bounded by some explicit function of k and the maximum size of a minor obstruction of \(\mathcal{G}\). This implies that the problem of deciding whether \(G\in \mathcal{G}^{(k)}\) is constructively fixed parameter tractable, when parameterized by k. Our results are based on a structural characterization of the obstructions of \(\mathcal{B}(\mathcal{G})\), relatively to the obstructions of \(\mathcal{G}\). Finally, we give two graph operations that generate members of \(\mathcal{G}^{(k)}\) from members of \(\mathcal{G}^{(k-1)}\) and we prove that this set of operations is complete for the class \(\mathcal{O}\) of outerplanar graphs. This yields the identification of all members \(\mathcal{O}\cap \mathcal{G}^{(k)}\), for every \(k\in \mathbb {N}\) and every non-trivial minor-closed graph class \(\mathcal{G}\).