k-apices of minor-closed graph classes. II. Parameterized algorithms

Abstract

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

37 pages, 3 figures