15
$\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$
  • $\begingroup$ Do you mean induced subgraph, instead of subgraph? $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 10 '12 at 13:46
  • $\begingroup$ @Kristoffer, I am interested in both. Have I missed something trivial about the non-induced case? $\endgroup$ – Raphael Aug 10 '12 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 Otachi Aug 10 '12 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 '12 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 Otachi Aug 12 '12 at 10:01
11
$\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$
11
$\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
    $\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 '13 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, privacy policy and cookie policy

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