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.
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:
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.