Résumé
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.