Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected.

Here an example: Let's say that D is as follow: enter image description here And T is the following tree: enter image description here

So I would like to identify the nodes and edges in D that can potentially match with T. In other words, I would like to color in red the set of nodes and edges that participate in any isomorphism from T to D. Something like this: enter image description here

What efficient algorithm can I use? I was reading about sub-graph isomorphism, but in my case, I don't have necessarily the label of edges, and I'm worried about the complexity. Are there other approaches?

About the output of the algorithm, the node P, for example, is red because don't exist any way that P with a combination of all their neighbor's nodes match with T due to his pattern which needs 4 consecutive nodes with edges pointing to the same direction, like a chain.

  • $\begingroup$ If you want to list every such correspondence, I think you can't do better than about $O(2^{n/2})$ time, because you could produce an output that big. Specifically: When $D$ contains $n$ numbered vertices and an edge from every vertex to every lower-numbered vertex, and $T$ is a path of $n/2$ vertices, then there is a correspondence for every element in a Sperner family). $\endgroup$ – j_random_hacker Apr 26 '18 at 12:15
  • $\begingroup$ If you only want to count the number of such correspondences, you might be able to do better. I would suggest trying to create a dynamic programming algorithm that computes $f(u, v)$, the number of subgraphs reachable from $u \in V(D)$ that are isomorphic to the subtree rooted at $v \in V(T)$. $\endgroup$ – j_random_hacker Apr 26 '18 at 12:16
  • $\begingroup$ So is your problem the subgraph isomorphism problem or not? I don't know what you mean by "identify nodes and edges that can potentially match" (potentially match? under what conditions does it count as a match? what does potentially mean?). Can you state the problem more clearly? You've told us what the inputs are. What do you want the algorithm to output? $\endgroup$ – D.W. Apr 26 '18 at 13:24
  • $\begingroup$ Well, I don't know the algorithm, that's my question. Should I use an algorithm like subgraph isomorphism or it's possible to use other alternatives... I updated the post to explain the expected output. $\endgroup$ – winter Apr 27 '18 at 7:23
  • $\begingroup$ From your edit it looks like you want to colour red the set of nodes and edges that do not participate in any isomorphism from $T$ to $D$. Is that right? $\endgroup$ – j_random_hacker Apr 27 '18 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.