16
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Do you mean induced subgraph, instead of subgraph? $\endgroup$ Aug 10, 2012 at 13:46
  • $\begingroup$ @Kristoffer, I am interested in both. Have I missed something trivial about the non-induced case? $\endgroup$
    – Simd
    Aug 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$ Aug 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$
    – Raphael
    Aug 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$ Aug 12, 2012 at 10:01

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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

$\endgroup$
1
  • 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$
    – Saeed
    Oct 1, 2013 at 9:13
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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