Parallelizability of the stack breadth-first search problem

The P-complete problem is known as a problem which is hard to be parallelized. In this paper, we consider parallelizability of a stack breadth-first search (stack BFS) problem which is proved to be P-complete. First we prove that the stack BFS if P-complete even if the maximum degree of an input graph is 3. Next we propose the longest path length (LPL) as a measure for P-completeness of the stack BFS. Using the measure, we propose an efficient parallel algorithm for the stack BFS. Assuming the size and LPL of an input graph is 0 and 1 respectively the complexity of the algorithm shows that the stack BFS is in NC if LPL - O(log (k) (n)) where k is a positive integer. In addition to this, the algorithm is cost optimal if LPL of an input graph is n and l respectively, the complexity of the algorithm shows that the stack BFS is in NC if L - O(log (k) n) where k is a positive integer. In addition to this, the algorithm is cost optimal if l = O (ne) where 0 < epsilon < 1.