# Subgraph isomorphism with a tree

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.

• Do you mean induced subgraph, instead of subgraph? Aug 10, 2012 at 13:46
• @Kristoffer, I am interested in both. Have I missed something trivial about the non-induced case?
– Simd
Aug 10, 2012 at 15:08
• Your problem is NP-hard even if $H$ is a path, since the longest (induced or non-induced) path problem is NP-hard. Aug 10, 2012 at 21:14
• 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. Aug 11, 2012 at 7:06
• The induced path problem is W-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. Aug 12, 2012 at 10:01

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$$).
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.
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. 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)$.
• 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)$). Oct 1, 2013 at 9:13
You are probably looking for Marx,Pilipczuk work on parameterized complexity of Subgraph Isomorphism. 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.