Search a tree with a tree?

Question

My problem:

1. I have a large tree with many nodes.
2. I would like to find a subset (group of nodes) of that tree.
3. The subset I am looking for is a (smaller) tree itself.

Part of the answer could contain a way to generate each permutation (possibility) of the target tree and then simply look through those for matches. But then you are still matching trees to trees. Keep in mind the tree I'm looking for may not start at the root.

I have mocked up an example of what I mean here:

https://i.stack.imgur.com/B995h.png

My questions are fairly simple:

• What branch of mathematics is this exactly?
• Are there any preexisting algorithms that have already been created to do this type of searching?

It seems like graph theory or maybe combinatorics but I really do not know. I just need some guidance on what to google so I can teach myself what to do.

Thanks in advance and sorry for not knowing more math jargon, I'm new here.

Thanks

Answer 1

What you are looking for is a tree matching algorithm. You can find a lot of information in this survey:

M. A. Tahraoui, K. Pinel-Sauvagnat, C. Laitang, M. Boughanem, H. Kheddouci, Lei Ning, A survey on tree matching and XML retrieval, Computer Science Review, Elsevier, (2013), vol. 8, pp. 1-23.

Other relevant bibliography includes the following papers:

[1] J. Burghardt, A tree pattern matching algorithm with reasonable space requirements, in: CAAP’88, (1988) 1–15.

[2] J. Cai, R. Paige, R.E. Tarjan, More efficient bottom-up tree pattern matching, in: CAAP’90, (1990) 72–86.

[3] D.R. Chase, An improvement to bottom-up tree pattern matching, in: POPL’87, (1987) 168–177.

[4] R. Cole, R. Hariharan, Tree pattern matching and subset matching in randomized $o(n \log^3 m)$ time, in: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA, (1997) 66–75.

[5] R. Cole, R. Hariharan, Tree pattern matching to subset matching in linear time, SIAM J. on Computing 32 (2003) 1056–1066.

[6] C.M. Hoffmann, M.J. O’Donnell, Pattern matching in trees, J. ACM (1982) 68–95

[7] S.R. Kosaraju, Efficient tree pattern matching, in: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, (1989) 178–183.