# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2105.05062.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., & Slusallek, J. (2021). Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal. Retrieved from https://arxiv.org/abs/2105.05062.

Cite as: https://hdl.handle.net/21.11116/0000-0008-E25F-F

##### 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-\varepsilon})$ 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 $\varepsilon > 0$ there exists $t \ge 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-\varepsilon})$.

Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight

lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there

exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$

Subgraph Isomorphism on pattern $H$ has no algorithm running in time

$O(n^{t+1-\varepsilon})$.

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,

and (4) a weighted problem variant.

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-\varepsilon})$ 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 $\varepsilon > 0$ there exists $t \ge 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-\varepsilon})$.

Under the more recent 3-uniform Hyperclique hypothesis, we even obtain tight

lower bounds for each specific treewidth $t \ge 3$: For any $t \ge 3$ there

exists a pattern graph $H$ of treewidth $t$ such that for any $\varepsilon>0$

Subgraph Isomorphism on pattern $H$ has no algorithm running in time

$O(n^{t+1-\varepsilon})$.

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,

and (4) a weighted problem variant.