Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number23
JournalACM Transactions on Algorithms
Volume19
Issue number3
DOIs
StatePublished - May 5 2023

Keywords

  • Topological minors
  • irrelevant vertex technique
  • treewidth
  • vertex deletion problems

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable'. Together they form a unique fingerprint.

Cite this