2026-07-25T22:07:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6275 2024-03-06T10:37:38Z ddc:004 open_access

Subexponential Time Algorithms for Embedding H-Minor Free Graphs Bodlaender, Hans L. Nederlof, Jesper van der Zanden, Tom C. subgraph isomorphism graph minors subexponential time 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Jesper Nederlof and Tom C. van der Zanden 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.9 urn:nbn:de:0030-drops-62756 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.9 eng https://creativecommons.org/licenses/by/3.0/legalcode