<p>It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper <a href="https://arxiv.org/abs/1307.2187" rel="nofollow noreferrer">Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)</a> by Marx and Pilipczuk. </p>

<p>Indeed, it follows from an earlier paper of Marx: <a href="http://www.theoryofcomputing.org/articles/v006a005/" rel="nofollow noreferrer">Can You Beat Treewidth? Theory of Computing 6(1): 85-112 (2010)</a> that a $f(k)n^{o(k/\log k)}$
time algorithm would violate the ETH. Here $n$ is the number of vertices in $H$ and $k$ is the number of vertices in $G$. This holds even when $G$ has max degree $3$ (but the degree of $H$ is unbounded).</p>

CC BY-SA 3.0
2017-02-24T13:58:26.377Z
2017-02-24T13:58:26.377Z
daniello
<p>Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ time assuming <strong>ETH</strong>. The easiest way to see this is to consider $G$ to be a clique and recall that $k$-clique problem requires $n^{\theta(k)}$ under <strong>ETH</strong> [1].</p>

<p>On the positive side, if $G$ is a path, a tree or a collection of small identical graphs we know how to solve Subgraph isomorphism in $f(|G|) |H|^{O(1)}$ time [2,3]. All these graphs are sparse, however I'm unaware of a general algorithm that runs in time $f(|G|) |H|^{O(1)}$, for all sparse graphs $G$. </p>

<p>My question is: do we know any conditional lower bounds for Subgraph isomorphism for sparse pattern graphs?</p>

<p>[1]<em>Chen, Jianer, et al. "Tight lower bounds for certain parameterized NP-hard problems." Information and Computation 201.2 (2005): 216-231.</em></p>

<p>[2]<em>Koutis, Ioannis, and Ryan Williams. "Limits and applications of group algebras for parameterized problems." International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg, 2009.</em></p>

<p>[3]<em>Fellows, Mike, et al. "Finding k disjoint triangles in an arbitrary graph." International Workshop on Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2004.</em></p>

CC BY-SA 3.0
2017-02-23T17:13:28.650Z
It is W-hard even when $G$ has maximum degree $3$, but FPT if $G$ has constant treewidth (all the above examples have constant treewidth). See https://arxiv.org/abs/1307.2187
daniello
CC BY-SA 3.0
2017-02-23T17:33:14.750Z
That looks extremely helpful, thank you! I'm embarrassed I've missed the paper.
ivmihajlin
CC BY-SA 3.0
2017-02-23T17:38:56.460Z
Maybe you just happen to know this: is any particular lower bound for bounded degree graphs (under ETH) follows from this paper?
ivmihajlin
CC BY-SA 3.0
2017-02-23T21:10:55.460Z
It follows from an earlier paper of Marx ("Can you beat treewidth") that a $f(k)n^{o(k/\log k)}$ time algorithm would violate the ETH. Here n is the number of vertices in H and k is the number of vertices in G. This holds even when G has max degree 3 (but the degree of H is unbounded)
daniello
CC BY-SA 3.0
2017-02-24T07:22:36.657Z
Thank you! This is exactly what I was looking for. If you don't mind, maybe you can write this comment as an answer so I can accept it?
ivmihajlin
<ds.algorithms><graph-algorithms><lower-bounds><parameterized-complexity><fine-grained>
Hardness of Subgraph isomorphism problem for sparse pattern graph
ivmihajlin
# Hardness of Subgraph isomorphism problem for sparse pattern graph

(Asked by: username_0 on 2017-02-23)

Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ time assuming **ETH**. The easiest way to see this is to consider $G$ to be a clique and recall that $k$-clique problem requires $n^{\theta(k)}$ under **ETH** [1].

On the positive side, if $G$ is a path, a tree or a collection of small identical graphs we know how to solve Subgraph isomorphism in $f(|G|) |H|^{O(1)}$ time [2,3]. All these graphs are sparse, however I'm unaware of a general algorithm that runs in time $f(|G|) |H|^{O(1)}$, for all sparse graphs $G$.

My question is: do we know any conditional lower bounds for Subgraph isomorphism for sparse pattern graphs?

[1]*Chen, Jianer, et al. "Tight lower bounds for certain parameterized NP-hard problems." Information and Computation 201.2 (2005): 216-231.*

[2]*Koutis, Ioannis, and Ryan Williams. "Limits and applications of group algebras for parameterized problems." International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg, 2009.*

[3]*Fellows, Mike, et al. "Finding k disjoint triangles in an arbitrary graph." International Workshop on Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2004.*

**Tags:** ds.algorithms, graph-algorithms, lower-bounds, parameterized-complexity, fine-grained

> **Comments:**
> **username_1**: It is W-hard even when $G$ has maximum degree $3$, but FPT if $G$ has constant treewidth (all the above examples have constant treewidth). See https://arxiv.org/abs/1307.2187  
> **username_0**: That looks extremely helpful, thank you! I'm embarrassed I've missed the paper.  
> **username_0**: Maybe you just happen to know this: is any particular lower bound for bounded degree graphs (under ETH) follows from this paper?  
> **username_1**: It follows from an earlier paper of Marx ("Can you beat treewidth") that a $f(k)n^{o(k/\log k)}$ time algorithm would violate the ETH. Here n is the number of vertices in H and k is the number of vertices in G. This holds even when G has max degree 3 (but the degree of H is unbounded)  
> **username_0**: Thank you! This is exactly what I was looking for. If you don't mind, maybe you can write this comment as an answer so I can accept it?  

---

## 1 answers

### Answer by username_1 on 2017-02-24. Score: 4 | Accepted answer

It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper [Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)](https://arxiv.org/abs/1307.2187) by Marx and Pilipczuk.

Indeed, it follows from an earlier paper of Marx: [Can You Beat Treewidth? Theory of Computing 6(1): 85-112 (2010)](http://www.theoryofcomputing.org/articles/v006a005/) that a $f(k)n^{o(k/\log k)}$
time algorithm would violate the ETH. Here $n$ is the number of vertices in $H$ and $k$ is the number of vertices in $G$. This holds even when $G$ has max degree $3$ (but the degree of $H$ is unbounded).


---

