5
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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 arxiv.org/abs/1307.2187 $\endgroup$
    – daniello
    Commented Feb 23, 2017 at 17:13
  • $\begingroup$ That looks extremely helpful, thank you! I'm embarrassed I've missed the paper. $\endgroup$
    – ivmihajlin
    Commented Feb 23, 2017 at 17:33
  • $\begingroup$ Maybe you just happen to know this: is any particular lower bound for bounded degree graphs (under ETH) follows from this paper? $\endgroup$
    – ivmihajlin
    Commented Feb 23, 2017 at 17:38
  • $\begingroup$ 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) $\endgroup$
    – daniello
    Commented Feb 23, 2017 at 21:10
  • $\begingroup$ 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? $\endgroup$
    – ivmihajlin
    Commented Feb 24, 2017 at 7:22

1 Answer 1

4
$\begingroup$

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) 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) 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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.