Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos · Society for Industrial and Applied Mathematics eBooks · 2019
For a finite collection of graphs , the -TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G\S does not contain any of the graphs in as a topological minor. We prove that for every such , -TM-Deletion is fixed parameter tractable on planar graphs. In particular, we provide an f(h, k) · n2 algorithm where h is an upper bound to the vertices of the graphs in .