Abstract
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. Our algorithm runs in a 2(k2) · n2 time, or, alternatively, in 2(k) · n4 time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface.
Original language | English (US) |
---|---|
Article number | 23 |
Journal | ACM Transactions on Algorithms |
Volume | 19 |
Issue number | 3 |
DOIs | |
State | Published - May 5 2023 |
Keywords
- Topological minors
- irrelevant vertex technique
- treewidth
- vertex deletion problems
ASJC Scopus subject areas
- Mathematics (miscellaneous)