Breadth-Depth Search is P-Complete.
Raymond Greenlaw · 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 P-complete. Specifically, we prove that if given a graph G = (V; E) either directed or undirected, a start vertex s 2 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 P-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...