<p>It can be solved in randomized expected time $O(2^km)$ where $k$ is the size of the small directed tree to be found and $m$ is the number of edges of the large directed graph in which to find it. See Theorem 6.1 of Alon, N., Yuster, R., and Zwick, U. (1995). Color-coding. <a href="http://doi.acm.org/10.1145/210332.210337">J. ACM 42(4): 844–856</a>. Alon et al. also state that their algorithm can be derandomized but don't give the details for that part; I think the deterministic time may be a little larger, something more like $O(k!\,m)$.</p>

CC BY-SA 3.0
2013-10-01T09:13:07.733Z
The derandomized version should be as usual, e.g like the way they described in section 4, just using perfect hash function to map $n$ nodes to $k$ color, which causes to extra $\log^2 n$ factor. (also can be improved to $\log n$ factor, means totally is $O(2^k \cdot m \cdot \log n)$).
Saeed
CC BY-SA 3.0
2013-09-27T21:01:17.903Z
2013-09-27T21:01:17.903Z
David Eppstein
<p>You are probably looking for Marx,Pilipczuk work on <a href="http://arxiv.org/abs/1307.2187" rel="nofollow">parameterized complexity of Subgraph Isomorphism</a>. Technically, it covers only undirected graphs, but I think you can adapt the hardness results for trees $H$ easily to rooted trees. The positive results relevant for your problem are already covered by the previous answers.</p>

CC BY-SA 3.0
2013-09-30T13:32:41.373Z
2013-10-01T13:37:41.490Z
2013-10-01T13:37:41.490Z
Radu Curticapean
<p>The question whether any fixed graph <span class="math-container">$H$</span> is an (induced) subgraph of <span class="math-container">$G$</span> is a first-order definable property, i.e., for every <span class="math-container">$H$</span> there is a formula <span class="math-container">$\varphi_H$</span> (<span class="math-container">$\psi_H$</span>) such that <span class="math-container">$H$</span> is an (induced) subgraph of <span class="math-container">$G$</span> if and only if <span class="math-container">$G \models \varphi_H$</span> (<span class="math-container">$G\models\psi_H$</span>).</p>
<p>It was formerly known that the model-checking problem is fixed-parameter tractable on classes of graphs that <a href="https://ieeexplore.ieee.org/document/4276571" rel="nofollow noreferrer">(locally) exclude a minor</a> and on classes of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.170.9781&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">(locally) bounded expansion</a>. Recently, Grohe, Kreutzer and S. anounced an even more general meta-theorem, stating that every first-order property can be decided in almost linear time on nowhere dense classes of graphs.</p>
<p>For your question this implies the following. Let <span class="math-container">$H$</span> be a fixed rooted tree. Then it can be decided in linear time whether <span class="math-container">$H$</span> is an (induced) subgraph of an input (directed or undirected) graph <span class="math-container">$G$</span> if <span class="math-container">$G$</span> is planar, or more generally is from a class that excludes a minor or from a class of bounded expansion. The problem can be decided in almost linear time if <span class="math-container">$G$</span> is from a class that locally excludes a minor or from a class of locally bounded expansion or most generally, <span class="math-container">$G$</span> is from a nowhere dense class of graphs.</p>

CC BY-SA 4.0
2013-09-27T07:35:11.073Z
2022-06-22T08:37:43.733Z
2022-06-22T08:37:43.733Z
Sebastian Siebertz
<p>If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$?  I am aware of results for subtree isomorphism where both $G$ and $H$ are trees and also where $G$ is planar or has bounded treewidth (and others) but not for this graph and tree case.  </p>

CC BY-SA 3.0
2012-08-10T13:46:18.117Z
Do you mean induced subgraph, instead of subgraph?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-08-10T15:08:14.820Z
@Kristoffer, I am interested in both.  Have I missed something trivial about the non-induced case?
Simd
CC BY-SA 3.0
2012-08-10T21:14:19.757Z
Your problem is NP-hard even if $H$ is a path, since the longest (induced or non-induced) path problem is NP-hard.
Yota Otachi
CC BY-SA 3.0
2012-08-11T07:06:27.493Z
Yes. I am interested in what more is known that is particular for $H$ being a tree.  For example, depending on properties of $G$ such as those in the question or assuming $H$ is fixed etc.
Raphael
CC BY-SA 3.0
2012-08-12T10:01:57.237Z
The induced path problem is W[1]-complete (Papadimitriou-Yannakakis 1991) while the (non-induced) path problem is FPT (Monien 1985). See also Chen-Flum 2007. I also want to know the parameterized complexity for other classes of trees.
Yota Otachi
<ds.algorithms><reference-request><graph-theory>
Subgraph isomorphism with a tree
Simd
# Subgraph isomorphism with a tree

(Asked by: username_0 on 2012-08-10)

If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$? I am aware of results for subtree isomorphism where both $G$ and $H$ are trees and also where $G$ is planar or has bounded treewidth (and others) but not for this graph and tree case.

**Tags:** ds.algorithms, reference-request, graph-theory

> **Comments:**
> **username_1**: Do you mean induced subgraph, instead of subgraph?  
> **username_0**: @Kristoffer, I am interested in both.  Have I missed something trivial about the non-induced case?  
> **username_2**: Your problem is NP-hard even if $H$ is a path, since the longest (induced or non-induced) path problem is NP-hard.  
> **username_3**: Yes. I am interested in what more is known that is particular for $H$ being a tree.  For example, depending on properties of $G$ such as those in the question or assuming $H$ is fixed etc.  
> **username_2**: The induced path problem is W[1]-complete (Papadimitriou-Yannakakis 1991) while the (non-induced) path problem is FPT (Monien 1985). See also Chen-Flum 2007. I also want to know the parameterized complexity for other classes of trees.  

---

## 3 answers

### Answer by username_7 on 2013-09-27. Score: 10 | Accepted answer

The question whether any fixed graph $H$ is an (induced) subgraph of $G$ is a first-order definable property, i.e., for every $H$ there is a formula $\varphi\_H$ ($\psi\_H$) such that $H$ is an (induced) subgraph of $G$ if and only if $G \models \varphi\_H$ ($G\models\psi\_H$).

It was formerly known that the model-checking problem is fixed-parameter tractable on classes of graphs that [(locally) exclude a minor](https://ieeexplore.ieee.org/document/4276571) and on classes of [(locally) bounded expansion](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.170.9781&rep=rep1&type=pdf). Recently, Grohe, Kreutzer and S. anounced an even more general meta-theorem, stating that every first-order property can be decided in almost linear time on nowhere dense classes of graphs.

For your question this implies the following. Let $H$ be a fixed rooted tree. Then it can be decided in linear time whether $H$ is an (induced) subgraph of an input (directed or undirected) graph $G$ if $G$ is planar, or more generally is from a class that excludes a minor or from a class of bounded expansion. The problem can be decided in almost linear time if $G$ is from a class that locally excludes a minor or from a class of locally bounded expansion or most generally, $G$ is from a nowhere dense class of graphs.


---

### Answer by username_4 on 2013-09-27. Score: 12

It can be solved in randomized expected time $O(2^km)$ where $k$ is the size of the small directed tree to be found and $m$ is the number of edges of the large directed graph in which to find it. See Theorem 6.1 of Alon, N., Yuster, R., and Zwick, U. (1995). Color-coding. [J. ACM 42(4): 844–856](http://doi.acm.org/10.1145/210332.210337). Alon et al. also state that their algorithm can be derandomized but don't give the details for that part; I think the deterministic time may be a little larger, something more like $O(k!\,m)$.

> **Comments:**
> **username_5**: The derandomized version should be as usual, e.g like the way they described in section 4, just using perfect hash function to map $n$ nodes to $k$ color, which causes to extra $\log^2 n$ factor. (also can be improved to $\log n$ factor, means totally is $O(2^k \cdot m \cdot \log n)$).  

---

### Answer by username_6 on 2013-09-30. Score: 3

You are probably looking for Marx,Pilipczuk work on [parameterized complexity of Subgraph Isomorphism](http://arxiv.org/abs/1307.2187). Technically, it covers only undirected graphs, but I think you can adapt the hardness results for trees $H$ easily to rooted trees. The positive results relevant for your problem are already covered by the previous answers.


---

