Document Open Access Logo

Subexponential Time Algorithms for Embedding H-Minor Free Graphs

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.9.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Hans L. Bodlaender, Jesper Nederlof, and Tom C. van der Zanden. Subexponential Time Algorithms for Embedding H-Minor Free Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.9

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.

Subject Classification

Keywords
  • subgraph isomorphism
  • graph minors
  • subexponential time

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos. Fast minor testing in planar graphs. Algorithmica, 64(1):69-84, 2012. Google Scholar
  2. Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4):801-808, 1990. Google Scholar
  3. Noga Alon, Raphy Yuster, and Uri Zwick. Color-coding: A New Method for Finding Simple Paths, Cycles and Other Small Subgraphs Within Large Graphs. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC'94, pages 326-335, New York, NY, USA, 1994. ACM. URL: http://dx.doi.org/10.1145/195058.195179.
  4. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Counting subgraphs via homomorphisms. SIAM Journal on Discrete Mathematics, 26(2):695-717, 2012. Google Scholar
  5. Hans L. Bodlaender. Treewidth: Algorithmic techniques and results. In Igor Prívara and Peter Ru\uzi\ucka, editors, Mathematical Foundations of Computer Science 1997, volume 1295 of Lecture Notes in Computer Science, pages 19-36. Springer Berlin Heidelberg, 1997. URL: http://dx.doi.org/10.1007/BFb0029946.
  6. Hans L. Bodlaender, Pal Gronas Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. An O(c^kn) 5-approximation algorithm for treewidth. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 499-508. IEEE, 2013. Google Scholar
  7. Hans L. Bodlaender and Jesper Nederlof. Subexponential Time Algorithms for Finding Small Tree and Path Decompositions. In Algorithms-ESA 2015, pages 179-190. Springer, 2015. Google Scholar
  8. Hans L. Bodlaender and Jesper Nederlof. Subexponential time algorithms for finding small tree and path decompositions. arXiv preprint arXiv:1601.02415, 2016. Google Scholar
  9. Hans L. Bodlaender and Johan M.M. Van Rooij. Exact algorithms for intervalizing colored graphs. In Theory and Practice of Algorithms in (Computer) Systems, pages 45-56. Springer, 2011. Google Scholar
  10. Paul Bonsma. Surface split decompositions and subgraph isomorphism in graphs on surfaces. arXiv preprint arXiv:1109.4554, 2011. Google Scholar
  11. Marek Cygan, Jakub Pachocki, and Arkadiusz Socała. The hardness of Subgraph Isomorphism. arXiv preprint arXiv:1504.02876, 2015. Google Scholar
  12. Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and PTASs. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 590-601. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  13. Frederic Dorn. Planar subgraph isomorphism revisited. arXiv preprint arXiv:0909.4692, 2009. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Parameterized complexity. Springer Science &Business Media, 2012. Google Scholar
  15. David Eppstein. Subgraph Isomorphism in Planar Graphs and Related Problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'95, pages 632-640, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics. Google Scholar
  16. Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin. Tight Bounds for Subgraph Isomorphism and Graph Homomorphism. arXiv preprint arXiv:1507.03738, 2015. Google Scholar
  17. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. arXiv preprint arXiv:1604.05999, 2016. Google Scholar
  18. Jakub Gajarskỳ, Petr Hliněnỳ, Jan Obdržálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. In Algorithms-ESA 2013, pages 529-540. Springer, 2013. Google Scholar
  19. Arvind Gupta and Naomi Nishimura. The complexity of subgraph isomorphism for classes of partial k-trees. Theoretical Computer Science, 164(1):287-298, 1996. Google Scholar
  20. MohammadTaghi Hajiaghayi and Naomi Nishimura. Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. Journal of Computer and System Sciences, 73(5):755-768, 2007. Google Scholar
  21. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424-435, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2011.07.004.
  22. Andrzej Lingas. Subgraph isomorphism for biconnected outerplanar graphs in cubic time. Theoretical Computer Science, 63(3):295-302, 1989. URL: http://dx.doi.org/10.1016/0304-3975(89)90011-X.
  23. Daniel Lokshtanov, Dániel Marx, Saket Saurabh, et al. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, (105):41-72, 2011. Google Scholar
  24. Dániel Marx. What is next? Future directions in parameterized complexity. In The Multivariate Algorithmic Revolution and Beyond, pages 469-496. Springer, 2012. Google Scholar
  25. Dániel Marx and Michał Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). arXiv preprint arXiv:1307.2187, 2013. Google Scholar
  26. Jiří Matoušek and Robin Thomas. On the complexity of finding iso-and other morphisms for partial k-trees. Discrete Mathematics, 108(1):343-364, 1992. Google Scholar
  27. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: http://dx.doi.org/10.1006/jctb.1995.1006.
  28. Maciej M. Sysło. The subgraph isomorphism problem for outerplanar graphs. Theoretical Computer Science, 17(1):91-97, 1982. URL: http://dx.doi.org/10.1016/0304-3975(82)90133-5.
  29. Dimitrios M. Thilikos. The Multivariate Algorithmic Revolution and Beyond. chapter Graph Minors and Parameterized Algorithm Design, pages 228-256. Springer-Verlag, Berlin, Heidelberg, 2012. Google Scholar
  30. Julian R. Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM (JACM), 23(1):31-42, 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact