### Subtree Isomorphism is in Random NC

**Authors:**

Gibbons, Phillip B.

Karp, Richard M.

Miller, Gary L.

Soroker, Danny
**Technical Report Identifier:** CSD-87-389
**December 2, 1987**

CSD-87-389.pdf

**Abstract:** Given two trees, a guest tree *G* and a host tree *H*, the subtree isomorphism problem is to determine whether there is a subgraph of *H* that is isomorphic to *G*. We present a randomized parallel algorithm for finding such an isomorphism, if it exists. The algorithm runs in time *O*(log^3 *n*) on a CREW PRAM, where *n* is the number of nodes in *H*. Randomization is used (solely) to solve each of a series of bipartite matching problems during the course of the algorithm. We demonstrate the close connection between the two problems by presenting a log space reduction from perfect bipartite matching to subtree isomorphism. Finally, we present some techniques to reduce the number of processors used by the algorithm.