Finding topological subgraphs is fixed-parameter tractable

We prove that for every fixed undirected graph H , there is an O(|V(G)| 3 ) time algorithm that, given a graph G , tests if G contains H as a topological subgraph (that is, a subdivision of H is subgraph of G ). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain an O(|V(G)| 3 ) time algorithm that tests if there is an immersion of H into a given graph G . This answers another open question raised by Downey and Fellows in 1992.

Authors

• Martin Grohe
• Ken-ichi Kawarabayashi
• Dániel Marx
• Paul Wollan

Keywords

• fixed-parameter tractability
• topological minors