An FPT-algorithm for recognizing $k$-apices of minor-closed graph classes

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Let ${\cal G}$ be a 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 prove that if ${\cal G}$ is minor-closed, then there is an algorithm that either returns a set $S$ certifying that $G$ is a $k$-apex of ${\cal G}$ or reports that such a set does not exist, in $2^{{\sf poly}(k)}\cdot n^3$ time. Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}$, i.e., the minor-minimal set of graphs not belonging to ${\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.

Knowledge Graph



Sign up or login to leave a comment