Block Elimination Distance

We introduce the 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 ${\cal G}^{(0)}={\cal B}({\cal G})$and,if$k\geq 1$,${\cal G}^{(k)}={\cal B}({\cal A}({\cal G}^{(k-1)}))$\mathrm{.}Theblockeliminationdistanceofagraph$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, 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 ${\cal G}$isminor-closedandwestudytheminorobstructionsetof${\cal 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{\cal G}^{(k)}$isconstructivelyfixedparametertractable,whenparameterizedby$k$. Our results are based on a structural characterization of the obstructions of $\mathcal{B}(\mathcal{G})$, relatively to the obstructions of $\mathcal{G}$. 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}$.