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.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Do you mean induced subgraph, instead of subgraph? $\endgroup$– Kristoffer Arnsfelt HansenAug 10, 2012 at 13:46
-
$\begingroup$ @Kristoffer, I am interested in both. Have I missed something trivial about the non-induced case? $\endgroup$– SimdAug 10, 2012 at 15:08
-
10$\begingroup$ Your problem is NP-hard even if $H$ is a path, since the longest (induced or non-induced) path problem is NP-hard. $\endgroup$– Yota OtachiAug 10, 2012 at 21:14
-
1$\begingroup$ 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. $\endgroup$– RaphaelAug 11, 2012 at 7:06
-
8$\begingroup$ 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. $\endgroup$– Yota OtachiAug 12, 2012 at 10:01
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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 and on classes of (locally) bounded expansion. 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.
answered Sep 27, 2013 at 7:35
$\begingroup$
$\endgroup$
1
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)$.
answered Sep 27, 2013 at 21:01
-
1$\begingroup$ 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)$). $\endgroup$– SaeedOct 1, 2013 at 9:13
$\begingroup$
$\endgroup$
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.
