BREADTH-DEPTH SEARCH IS ${\mathcal P}$-COMPLETE
Raymond Greenlaw · Parallel Processing Letters · 1993
The parallel complexity of a search strategy that combines attributes of both breadth-first search and depth-first search is studied. The search called breadth-depth search was defined by Horowitz and Sahni. The search technique has applications in branch-and-bound strategies. Kindervater and Lenstra posed the complexity of this type of search strategy as an open problem. We resolve their question by showing that a natural decision problem based on breadth-depth search is [Formula: see text]-complete. Specifically, we prove that if given a graph G=(V, E) either directed or undirected, a start vertex s∈V, and two designated vertices u and v in V, then the problem of deciding whether u is visited before v by a breadth-depth search originating from s is [Formula: see text]-complete. The search can be based either on vertex numbers or fixed ordered adjacency lists. Our reductions differ for directed/undirected graphs and depending on whether vertex numbers/fixed ordered adjacency lists are used. These results indicate breadth-depth search is highly sequential in nature and probably will not adapt to a fast parallel solution, unless [Formula: see text] equals [Formula: see text].