← All Problems
P-complete

Lexicographically First Depth-first Search Ordering (LFDFS)

Category: Searching Graphs

Input

An undirected graph $G = (V, E)$ with fixed ordered adjacency lists, and two designated vertices $u$ and $v$.

Problem

Is vertex $u$ visited before vertex $v$ in the depth-first search of $G$ induced by the order of the adjacency lists?

Status

$\P$-complete (Reif [1]).

Remarks

The reduction to show hardness is from LFMP.

The directed case can be reduced to the undirected case easily. The reduction is dependent on the adjacency lists fixing the order in which the adjacent vertices are examined. The problem remains open if this constraint is relaxed. For example, the problem remains open for graphs presented with all adjacency lists sorted in order of increasing vertex number. The problem remains $\P$-complete if the input graph is given with a fixed vertex numbering and the search order is based on this numbering rather than the fixed ordered adjacency lists ([2], Greenlaw [3]). Anderson showed that computing just the first branch of the lexicographically first DFS tree, called the lexicographically first maximal path, is $\P$-complete [2], see LFMP.

Computing the LFDFS tree in planar graphs is $\P$-complete as well [2]. However, Planar Directed Depth-first Search is in $\NC$ (Kao [4]). The depth-first search tree constructed in [4] is not the lexicographically first. Hagerup shows that a depth-first search tree can be constructed in a planar graph on a PRIORITY CRCW-PRAM using $O(\log n)$ time and $n^3$ processors [5]. In $\mathsf{RNC}$, it is possible to find some depth-first vertex numbering and the depth-first spanning tree corresponding to it; see DFS. Computing a depth-first vertex numbering for planar graphs is in $\NC$ (He and Yesha [6], Smith [7]). Computing the lexicographically first depth-first numbering for directed acyclic graphs is in $\NC$ (de la Torre and Kruskal [8][9], Greenlaw [10], Zhang [11]). Determining whether a directed spanning tree of a general graph has a valid DFS numbering is in $\NC$ (Schevon and Vitter [12]). Vitter and Simons give a $\sqrt{n}$ time parallel algorithm for the non-sparse version of the problem [13]. Computing a LFDFS in a tree structured or outerplanar graph is in $\NC$ (Chlebus et al. [14]).

References

  1. J. H. Reif (1985). Depth-first search is inherently sequential.
  2. R. J. Anderson (1985). The Complexity of Parallel Algorithms.
  3. R. Greenlaw (1988). The Complexity of Parallel Computations: Inherently Sequential Algorithms and P-Complete Problems.
  4. M.-Y. Kao (1991). All graphs have cycle separators and planar directed depth-first search is in DNC.
  5. T. Hagerup (1990). Planar depth-first search in O(log n) parallel time.
  6. X. He and Y. Yesha (1988). A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs.
  7. J. R. Smith (1986). Parallel algorithms for depth first searches I: Planar graphs.
  8. P. de la Torre and C. P. Kruskal (1989). Fast parallel algorithms for all sources lexicographic search and path finding problems.
  9. 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.
  10. R. Greenlaw (1992). A model classifying algorithms as inherently sequential with applications to graph searching.
  11. Y. Zhang (1986). Parallel Algorithms for Problems Involving Directed Graphs.
  12. C. A. Schevon and J. S. Vitter (1988). A parallel algorithm for recognizing unordered depth-first search.
  13. J. S. Vitter and R. A. Simons (1986). New classes for parallel complexity: A study of unification and other complete problems for P.
  14. B. Chlebus, K. Diks, W. Rytter, and T. Szymacha (1989). Parallel complexity of lexicographically first problems for tree-structured graphs.
  15. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.3.3.

Related Problems