Let ${ \cal G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of ${ \cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${ \cal G}$. We denote by ${ \cal A}_k ({ \cal G})$ the set of all graphs that are $k$-apices of ${ \cal G}.$ In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of ${ \cal A}_k ({ \cal G})$, i.e., the minor-minimal set of graphs not belonging to ${ \cal A}_k ({ \cal G}).$ In this article we provide an algorithm that, given a graph $G$ on $n$ vertices, runs in $2^{ { \sf poly}(k)}\cdot n^3$-time and either returns a set $S$ certifying that $G \in { \cal A}_k ({ \cal G})$, or reports that $G \notin { \cal A}_k ({ \cal G})$. Here ${ \sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${ \cal G}.$ In the special case where ${ \cal G}$ excludes some apex graph as a minor, we give an alternative algorithm running in $2^{ { \sf poly}(k)}\cdot n^2$-time.
Categories: cs.DS cs.CC math.CO