Subtree isomorphism is in random NC.

*(English)*Zbl 0711.68052A 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 D. W. Matula [Annals of Discrete Mathematics 2, 91-106 (1978; Zbl 0391.05022)], combined with the dynamic contraction technique by G. L. Miller and 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 K. Mulmuley, U. V. Vazirani and 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.

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 D. W. Matula [Annals of Discrete Mathematics 2, 91-106 (1978; Zbl 0391.05022)], combined with the dynamic contraction technique by G. L. Miller and 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 K. Mulmuley, U. V. Vazirani and 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.

Reviewer: J.Vyskoc

##### MSC:

68W15 | Distributed algorithms |

68R10 | Graph theory (including graph drawing) in computer science |

68Q25 | Analysis of algorithms and problem complexity |

PDF
BibTeX
XML
Cite

\textit{P. B. Gibbons} et al., Discrete Appl. Math. 29, No. 1, 35--62 (1990; Zbl 0711.68052)

Full Text:
DOI

##### References:

[1] | Borodin, A.; von zur Gathen, J.; Hopcroft, J.E., Fast parallel matrix and GCD computations, Proceedings of the symposium on foundations of computer science (FOCS), 65-71, (1982) · Zbl 0507.68020 |

[2] | Brent, R.P., The parallel evaluation of general arithmetic expressions, J. ACM, 21, 201-208, (1974) · Zbl 0276.68010 |

[3] | D. Coppersmith, personal communication, 1988. |

[4] | Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, Proceedings of the symposium on theory of computing (STOC), 1-6, (1987) |

[5] | Edmonds, J., Systems of distinct representatives and linear algebra, J. res. nat. bur. standards, 71, 241-245, (1967) · Zbl 0178.03002 |

[6] | Galil, Z.; Pan, V., Improved processor bounds for algebraic and combinatorial problems in RNC, (), 490-495 · Zbl 0685.68048 |

[7] | Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP completeness, (1979), Freeman New York · Zbl 0411.68039 |

[8] | Gibbons, P.B.; Karp, R.M.; Miller, G.L.; Soroker, D., Subtree isomorphism is in random NC, (), 43-52, Lecture Notes in Computer Science |

[9] | Gibbons, P.B.; Karp, R.M.; Miller, G.L.; Soroker, D., Subtree isomorphism is in random NC, () · Zbl 0652.68078 |

[10] | P.B. Gibbons, G.L. Miller and S.-H. Teng, personal communication,1988. |

[11] | Karp, R.M.; Ramachandran, V.L., A survey of parallel algorithms for shared-memory machines, (), also in: Handbook of Theoretical Computer Science (North-Holland, Amsterdam, to appear) |

[12] | Karp, R.M.; Upfal, E.; Wigderson, A., Constructing a perfect matching is in random NC, Combinatorica, 6, 1, 35-48, (1986) · Zbl 0646.05051 |

[13] | M. Karpinski and A. Lingas, Subtree isomorphism and bipartite perfect matching are mutually NC reducible, Submitted. · Zbl 0664.68072 |

[14] | Ladner, R.E.; Fischer, M.J., Parallel prefix computation, J. ACM, 27, 4, 831-838, (1980) · Zbl 0445.68066 |

[15] | Matula, D.W., Subtree isomorphism in O(n\(52\)), (), 91-106 · Zbl 0391.05022 |

[16] | Miller, G.L.; Reif, J.H., Parallel tree contraction and its applications, Proceedings of the symposium on foundations of computer science (FOCS), 478-489, (1985) |

[17] | Mulmuley, K.; Vazirani, U.V.; Vazirani, V.V., Matching is as easy as matrix inversion, Combinatorica, 7, 1, 105-113, (1987) · Zbl 0632.68041 |

[18] | Pan, V., Fast and efficient parallel algorithms for the exact inversion of integer matrices, (), 504-521, Lecture Notes in Computer Science |

[19] | Pippenger, N., On simultaneous resource bounds, Proceedings of the symposium on foundations of computer science (FOCS), 307-311, (1979) |

[20] | Preparata, F.P.; Sarwate, D.V., An improved parallel processor bound in fast matrix inversion, Inform. process. lett., 7, 3, 148-150, (1978) · Zbl 0373.65020 |

[21] | Rabin, M.O.; Vazirani, V.V., Maximum matchings in general graphs through randomization, () · Zbl 0689.68092 |

[22] | Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 701-717, (1980) · Zbl 0452.68050 |

[23] | Stockmeyer, L.J.; Vishkin, U., Simulation of parallel random access machines by circuits, SIAM J. comput., 13, 409-422, (1984) · Zbl 0533.68048 |

[24] | Tarjan, R.E.; Vishkin, U., An efficient parallel biconnectivity algorithm, SIAM J. comput., 14, 862-874, (1985) · Zbl 0575.68066 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.