License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.9
URN: urn:nbn:de:0030-drops-62756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6275/
Go to the corresponding LIPIcs Volume Portal

Bodlaender, Hans L. ; Nederlof, Jesper ; van der Zanden, Tom C.

Subexponential Time Algorithms for Embedding H-Minor Free Graphs

pdf-format:
LIPIcs-ICALP-2016-9.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bodlaender_et_al:LIPIcs:2016:6275,
  author =	{Hans L. Bodlaender and Jesper Nederlof and Tom C. van der Zanden},
  title =	{{Subexponential Time Algorithms for Embedding H-Minor Free Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6275},
  URN =		{urn:nbn:de:0030-drops-62756},
  doi =		{10.4230/LIPIcs.ICALP.2016.9},
  annote =	{Keywords: subgraph isomorphism, graph minors, subexponential time}
}

Keywords: subgraph isomorphism, graph minors, subexponential time
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI