κ-Apices of Minor-closed Graph Classes. II. Parameterized Algorithms

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