ELC Seminar (A03)
| Time & Date | Feb. 15(Mon) 2016, 14:00 ~ 15:30 | |
|---|---|---|
| Place | CELC Seminar room (Rm. 404) | |
| Speaker | Hans L. Bodlaender | |
| Title | Subexponential time algorithms for graph embedding problems on H-minor free graphs |
|
| Abstract | ||
|---|---|---|
| In this talk, a number of graph embedding problems are considered: given a graph G and a graph P, is P isomorphic to a subgraph of G, is P isomorphic to an induced subgraph of G, is P a minor of G, and is P an induced minor of G. For each of these problems, there is an algorithm that uses 2^O(n/log n) time when there is a fixed graph H such that G does not contain H as a minor. Amongst others, this implies an algorithm for subgraph isomorphism, induced subgraph isomorphism, minor testing or induced minors for planar graphs and graphs with bounded treewidth with this running time. We also show that the result is tight: assuming the exponential time hypothesis, there is no algorithm for graphs of pathwidth 3 with 2^o(n/log n) unning time for each of these problems. Similar algorithms and lower bounds exist for the Intervalizing k-colored graphs problem, and the problem to find path or tree decompositions of bounded width with a minimum number of bags. This is joint work with Tom van der Zanden, Jesper Nederlof, and Johan van Rooij. (Host: Yota Otachi) |
||