1 Search Results for "Slusallek, Jasper"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.40
Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal

Authors: Karl Bringmann and Jasper Slusallek

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The Subgraph Isomorphism problem is of considerable importance in computer science. We examine the problem when the pattern graph H is of bounded treewidth, as occurs in a variety of applications. This problem has a well-known algorithm via color-coding that runs in time O(n^{tw(H)+1}) [Alon, Yuster, Zwick'95], where n is the number of vertices of the host graph G. While there are pattern graphs known for which Subgraph Isomorphism can be solved in an improved running time of O(n^{tw(H)+1-ε}) or even faster (e.g. for k-cliques), it is not known whether such improvements are possible for all patterns. The only known lower bound rules out time n^{o(tw(H) / log(tw(H)))} for any class of patterns of unbounded treewidth assuming the Exponential Time Hypothesis [Marx'07]. In this paper, we demonstrate the existence of maximally hard pattern graphs H that require time n^{tw(H)+1-o(1)}. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from fine-grained complexity theory, we prove the following asymptotic statement for large treewidth t: For any ε > 0 there exists t ≥ 3 and a pattern graph H of treewidth t such that Subgraph Isomorphism on pattern H has no algorithm running in time O(n^{t+1-ε}). Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight lower bounds for each specific treewidth t ≥ 3: For any t ≥ 3 there exists a pattern graph H of treewidth t such that for any ε > 0 Subgraph Isomorphism on pattern H has no algorithm running in time O(n^{t+1-ε}). In addition to these main results, we explore (1) colored and uncolored problem variants (and why they are equivalent for most cases), (2) Subgraph Isomorphism for tw < 3, (3) Subgraph Isomorphism parameterized by pathwidth instead of treewidth, and (4) a weighted variant that we call Exact Weight Subgraph Isomorphism, for which we examine pseudo-polynomial time algorithms. For many of these settings we obtain similarly tight upper and lower bounds.
Cite as

Karl Bringmann and Jasper Slusallek. Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ICALP.2021.40,
  author =	{Bringmann, Karl and Slusallek, Jasper},
  title =	{{Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.40},
  URN =		{urn:nbn:de:0030-drops-141095},
  doi =		{10.4230/LIPIcs.ICALP.2021.40},
  annote =	{Keywords: subgraph isomorphism, treewidth, fine-grained complexity, hyperclique}
}
  • Refine by Author
  • 1 Bringmann, Karl
  • 1 Slusallek, Jasper

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 fine-grained complexity
  • 1 hyperclique
  • 1 subgraph isomorphism
  • 1 treewidth

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact