2010/11/08 by Martin Grohe, Grohe, Martin, Ken‐ichi Kawarabayashi +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1011.1827
openalex publication_date 2010/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for every fixed undirected graph H, there is a O(|V(G)|3) time algorithm that tests, given a graph G, 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.