Subtree isomorphism is in random NC (Q922707): Difference between revisions

A subtree isomorphism problem is to determine for given two trees G and H whether there is a subgraph (subtree) of H that is isomorphic to G. Unlike other versions of the (sub)graph isomorphism problem this one is known to be in P, yet the existence of a fast parallel algorithm to solve it posses an interesting problem. The authors answer this problem affirmatively, provided that we consider randomized parallel algorithms. Their algorithm runs in time \(O(\log^ 3 n)\) on a CREW PRAM using \(n^ 3M(n)\log \log n/\log n\) processors, where M(n) is the number of bit operations required by a CREW PRAM to multiply two \(n\times n\) boolean matrices in O(log n) time. The authors start with the description of an algorithm for solving the rooted version of the subtree isomorphism problem, whic is then extended to the general unrooted case. Their approach is based on the best known sequential algorithm for this problem, given by \textit{D. W. Matula} [Annals of Discrete Mathematics 2, 91-106 (1978; Zbl 0391.05022)], combined with the dynamic contraction technique by \textit{G. L. Miller} and \textit{J. H. Reif} [Parallel tree contraction and its application, Proc. Symp. on Foundations of Computer Science, 478-489 (1985)]. The randomized part of their algorithm is derived from using the randomized algorithm of \textit{K. Mulmuley}, \textit{U. V. Vazirani} and \textit{V. V. Vazirani} [Combinatorica 7(1), 105-113 (1987; Zbl 0632.68041)] for constructing a perfect matching in a bipartite graph. Finally they prove that bipartite perfect matching is log-space irreducible to subtree isomorphism.