Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Journal article, Peer reviewed
Published version
Åpne
Permanent lenke
https://hdl.handle.net/11250/2755661Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
- Department of Informatics [928]
- Registrations from Cristin [9791]
Originalversjon
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 2020, 931–950Sammendrag
For a finite collection of graphs F, the F-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 F as a topological minor. We prove that for every such F, F-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 F.