Subtree Isomorphism (STI)
Category: Network Flows
Input
Two unrooted trees $T = (V, E)$ and $T’ = (V’, E’)$.
Problem
Is $T$ isomorphic to a subtree of $T’$?
Definitions
See BDGI.
Status
Open.
Remarks
$\mathsf{RNC}^3$ algorithms for the problem were developed independently in [1][2]. Each uses randomization solely to solve a number of Bipartite Matching Problems, see PME. Lindell shows that the problem of determining whether two unrooted trees are isomorphic, namely the Tree Isomorphism Problem, can be solved in $\mathsf{DLOG}$; therefore, on an EREW-PRAM in $O(\log n)$ time using $n^{O(1)}$ processors [3].
References
- P. B. Gibbons, R. M. Karp, G. L. Miller, and D. Soroker (1990). Sub-tree isomorphism is in Random NC.
- A. Lingas and M. Karpinski (1989). Subtree isomorphism is NC reducible to bipartite perfect matching.
- S. Lindell (1992). A logspace algorithm for tree canonization.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.9.9.