Parallel complexity of computing a maximal set of disjoint paths

Abstract

Given a graph, G = (V, E), and sets S ⊂ V and Q ⊂ V, the maximal paths problem requires the computation of a maximal set of vertex disjoint paths in G that begin at vertices of S and end at vertices of Q. It is well known that this problem can be solved sequentially in time that is proportional to the number of edges in G. However, its parallel complexity is not known. This note shows that this problem is NC-reducible to that of computing a depth-first search forest in a suitable n-vertex graph. This result can also be extended to directed graphs. © 1992.