On the complexity of topological sorting (Q750150)

If a digraph is acyclic (has no directed cycles), a polynomial sequential algorithm can perform a topological sort on its vertices - that is, label them 1,2,...,n so that arcs go only from vertices with smaller labels to vertices with larger labels. The parallel complexity of this problem has been successively reduced from \(NC^ 2\) to \(NL^*\) to \(FL^{NL}\) [see \textit{S. A. Cook}, Inf. Control 64, 2-22 (1985; Zbl 0575.68045) for definitions of parallel complexity classes]. In Cook [loc. cit.] the problem was posed as to whether this problem is NL (non-deterministic log-space)-hard under \(NC^ 1\)-reducibility and answered in the affirmative if the algorithm is required to state whether the digraph is acyclic (since deciding whether a digraph is acyclic is NL-hard) but left open otherwise. The author shows that topological sorting is NL-hard even if the algorithm is required merely to topologically sort a digraph which happens to be acyclic and is allowed to label its vertices arbitrarily otherwise. In case the graph has no cycles, directed or undirected, the article presents a DL (deterministic log-space) topological sorting algorithm. It was shown in \textit{S. A. Cook} and \textit{P. McKenzie} [J. Algorithms 8, 385-394 (1987; Zbl 0644.68058)] that deciding whether an undirected graph is acyclic is DL-complete; the article under review proves that topological sorting is DL-complete even if the algorithm is not required to state whether the underlying undirected graph is acyclic.