Theoretical Computer Science
- ds.algorithms graph-algorithms lower-bounds parameterized-complexity fine-grained
- Updated Wed, 22 Jun 2022 08:19:34 GMT
-
Hardness of Subgraph isomorphism problem for sparse pattern graph
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.
Solution
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).
External Links
External links referenced by this document: