Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Abstract

For a finite collection of graphs $\mathcal{F}$, the \textsc{$\mathcal{F}$-TM-Deletion} problem has as input an $n$-vertex graph $G$ and an integer $k$ and asks whether there exists a set $S\subseteq V(G)$ with $|S|\le k$ such that $G\setminus S$ does not contain any of the graphs in $\mathcal{F}$ as a topological minor. We prove that for every such $\mathcal{F}$, \textsc{$\mathcal{F}$-TM-Deletion} is fixed parameter tractable on planar graphs. Our algorithm runs in a $2^{\mathcal{O}(k^2)}\cdot n^2$ time or, alternatively in $2^{\mathcal{O}(k)}\cdot n^4$ time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface.

A preliminary version of these results appeared in [Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos: Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable. SODA 2020: 931-950]