Stack Breadth-first Search (SBFS)
Input
An undirected graph $G = (V, E)$ with a numbering on the vertices, and two designated vertices $u$ and $v$.
Problem
Is vertex $u$ visited before vertex $v$ in the stack breadth-first search of $G$ induced by the vertex numbering?
Definitions
A stack breadth-first search is a breadth-first search that is implemented using a stack. The vertices most recently visited on a new level are searched from first at the next level.
Status
$\P$-complete (Greenlaw [1][2]).
Remarks
The reduction to show hardness is from SAM2CVP. The Lexicographic Breadth-first Search Problem, which has a natural implementation on a queue, is defined as follows: given a graph $G$ with fixed ordered adjacency lists, is vertex $u$ visited before vertex $v$ in the breadth-first search of $G$ induced by the order of the adjacency lists? This problem is in $\NC$ (de la Torre and Kruskal [3][4], Greenlaw [1]).
References
- R. Greenlaw (1988). The Complexity of Parallel Computations: Inherently Sequential Algorithms and P-Complete Problems.
- R. Greenlaw (1992). A model classifying algorithms as inherently sequential with applications to graph searching.
- P. de la Torre and C. P. Kruskal (1989). Fast parallel algorithms for all sources lexicographic search and path finding problems.
- P. de la Torre and C. P. Kruskal (1991). Fast and efficient parallel algorithms for single source lexicographic depth-first search, breadth-first search and topological-first search.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.3.5.