Abstract
We introduce the parameter of {\sl block elimination distance} as a measure of how closea graph is to some particular graph class. Formally, given a graph class ${\cal G}$, the class ${\cal B}({\cal G})$ contains all graphs whose blocks belong to ${\cal G}$and the class ${\cal A}({\cal G})$ contains all graphs where the removal of a vertex creates a graph in ${\cal G}$. Given a hereditary graph class ${\cal G}$, we recursively define ${\cal 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)}))$.We show that, for every non-trivial hereditary class ${\cal G}$, the problem of deciding whether $G\in{\cal G}^{(k)}$ is {\sf NP}-complete.We focus on the case where ${\cal G}$ is minor-closed and we study the minor obstruction set of ${\cal G}^{(k)}$ i.e., the minor-minimal graphs not in ${\cal G}^{(k)}$.We prove that the size of the obstructions of ${\cal G}^{(k)}$ is upper bounded by some explicit function of $k$ and the maximum size of a minor obstruction of ${\cal G}$.This implies that the problem of deciding whether $G\in{\cal G}^{(k)}$ is {\sl constructively} fixed parameter tractable, when parameterized by $k$.Finally, we give two graph operations that generate members of ${\cal G}^{(k)}$ from members of ${\cal G}^{(k-1)}$ and we prove that this set of operations is complete for the class ${\cal O}$ of outerplanar graphs.