Résumé
Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G \ S belongs to G. We denote by Ak(G) the set of all graphs that are k-apices of G. In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of Ak(G), i.e., the minor-minimal set of graphs not belonging to Ak(G). In this article we provide an algorithm that, given a graph G on n vertices, runs in time 2poly(k) · n3 and either returns a set S certifying that G ∈ Ak(G), or reports that G ∈/ Ak(G). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2poly(k) · n2-time.