TY - GEN

T1 - Subexponential Time Algorithms for Embedding H-Minor Free Graphs

AU - Bodlaender, Hans

AU - Nederlof, Jesper

AU - van der Zanden, Tom

PY - 2016

Y1 - 2016

N2 - We establish the complexity of several graph embedding problems: Subgraph Isomorphism, Graph Minor, Induced Subgraph and Induced Minor, when restricted to H-minor free graphs. In each of these problems, we are given a pattern graph P and a host graph G, and want to determine whether P is a subgraph (minor, induced subgraph or induced minor) of G. We show that, for any fixed graph H and epsilon > 0, if P is H-Minor Free and G has treewidth tw, (induced) subgraph can be solved 2^{O(k^{epsilon}*tw+k/log(k))}*n^{O(1)} time and (induced) minor can be solved in 2^{O(k^{epsilon}*tw+tw*log(tw)+k/log(k))}*n^{O(1)} time, where k = |V(P)|. We also show that this is optimal, in the sense that the existence of an algorithm for one of these problems running in 2^{o(n/log(n))} time would contradict the Exponential Time Hypothesis. This solves an open problem on the complexity of Subgraph Isomorphism for planar graphs. The key algorithmic insight is that dynamic programming approaches can be sped up by identifying isomorphic connected components in the pattern graph. This technique seems widely applicable, and it appears that there is a relatively unexplored class of problems that share a similar upper and lower bound.

AB - We establish the complexity of several graph embedding problems: Subgraph Isomorphism, Graph Minor, Induced Subgraph and Induced Minor, when restricted to H-minor free graphs. In each of these problems, we are given a pattern graph P and a host graph G, and want to determine whether P is a subgraph (minor, induced subgraph or induced minor) of G. We show that, for any fixed graph H and epsilon > 0, if P is H-Minor Free and G has treewidth tw, (induced) subgraph can be solved 2^{O(k^{epsilon}*tw+k/log(k))}*n^{O(1)} time and (induced) minor can be solved in 2^{O(k^{epsilon}*tw+tw*log(tw)+k/log(k))}*n^{O(1)} time, where k = |V(P)|. We also show that this is optimal, in the sense that the existence of an algorithm for one of these problems running in 2^{o(n/log(n))} time would contradict the Exponential Time Hypothesis. This solves an open problem on the complexity of Subgraph Isomorphism for planar graphs. The key algorithmic insight is that dynamic programming approaches can be sped up by identifying isomorphic connected components in the pattern graph. This technique seems widely applicable, and it appears that there is a relatively unexplored class of problems that share a similar upper and lower bound.

U2 - 10.4230/LIPIcs.ICALP.2016.9

DO - 10.4230/LIPIcs.ICALP.2016.9

M3 - Conference contribution

SN - 978-3-95977-013-2

VL - 55

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 14

BT - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

A2 - Ioannis Chatzigiannakis Michael Mitzenmacher, Yuval Rabani

A2 - Sangiorgi, Davide

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

CY - Dagstuhl, Germany

ER -