  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.
