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 wellknown algorithm via colorcoding 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 kcliques), 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)+1o(1)}. Specifically, under the Strong Exponential Time Hypothesis (SETH), a standard assumption from finegrained 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 3uniform 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 pseudopolynomial time algorithms. For many of these settings we obtain similarly tight upper and lower bounds.
BibTeX  Entry
@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:140:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14109},
URN = {urn:nbn:de:0030drops141095},
doi = {10.4230/LIPIcs.ICALP.2021.40},
annote = {Keywords: subgraph isomorphism, treewidth, finegrained complexity, hyperclique}
}
Keywords: 

subgraph isomorphism, treewidth, finegrained complexity, hyperclique 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 