Basic applications of parallel matching

Abstract In this chapter we present some natural applications of parallel algorithms for maximum matchings. We show that due to RNC-algorithms for maximum matchings there exist RNC-algorithms for the following problems: maximum disjoint paths, optimal flows in some networks, DFS-tree construction and subtree isomorphism. If there is an NC-algorithm for maximum matchings then there are NC-algorithms for each of the above problems. Hence the maximum matching problem is the main representative of an important class of combinatorial problems NC-reducible to it. Two unrooted undirected trees T’, T” are isomorphic (we write T’ = T”) iff they have the same shape, that is iff they are isomorphic in the sense of undirected unlabeled graphs. There are linear time sequential algorithms and optimal NC¬ algorithms to test tree isomorphism. However, the problem of subtree isomorphism is much more complex. The subtree isomorphism problem can be defined as follows: there are two trees Tl, T2, test if there is a subtree T of T2 such that Tl= T2. The main result of this section is an RNC-algorithm for the subtree isomorphism problem. We also show that this problem is in NC if and only if the perfect matching problem for bipartite graphs is in NC. It is usually much easier to deal with rooted directed trees: two such trees T’, T” are isomorphic iff there is a bijection between their sets of nodes such that the roots correspond to each other, and the bijection preserves the relation “to be a father of” .