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.
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. © 2011 ACM.
Finding topological subgraphs is fixed-parameter tractable / Martin, Grohe; Ken Ichi, Kawarabayashi; Daniel, Marx; Wollan, PAUL JOSEPH. - STAMPA. - (2011), pp. 479-488. (Intervento presentato al convegno 43rd ACM Symposium on Theory of Computing, STOC'11 tenutosi a San Jose, CA nel 6 June 2011 through 8 June 2011) [10.1145/1993636.1993700].
Finding topological subgraphs is fixed-parameter tractable
WOLLAN, PAUL JOSEPH
2011
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
