computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, st-connectivity or STCON is a

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

asking, for vertices ''s'' and ''t'' in a directed graph, if ''t'' is reachable from ''s''. Formally, the decision problem is given by :.

Complexity

On a sequential computer, st-connectivity can easily be solved in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

by either

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...

or breadth-first search. The interest in this problem in computational complexity concerns its complexity with respect to more limited forms of computation. For instance, the

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

of problems that can be solved by a non-deterministic Turing machine using only a logarithmic amount of memory is called NL. The st-connectivity problem can be shown to be in NL, as a non-deterministic Turing machine can guess the next node of the path, while the only information which has to be stored is the total length of the path and which node is currently under consideration. The algorithm terminates if either the target node ''t'' is reached, or the length of the path so far exceeds ''n'', the number of nodes in the graph. The complement of ''st-connectivity'', known as ''st-non-connectivity'', is also in the class NL, since NL = coNL by the

Immerman–Szelepcsényi theorem In computational complexity theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for wh ...

. In particular, the problem of ''st-connectivity'' is actually NL-complete, that is, every problem in the class NL is reducible to connectivity under a log-space reduction. This remains true for the stronger case of first-order reductions . The log-space reduction from any language in NL to STCON proceeds as follows: Consider the non-deterministic log-space Turing machine M that accepts a language in NL. Since there is only logarithmic space on the work tape, all possible states of the Turing machine (where a state is the state of the internal finite state machine, the position of the head and the contents of the work tape) are polynomially many. Map all possible states of the deterministic log-space machine to vertices of a graph, and put an edge between u and v if the state v can be reached from u within one step of the non-deterministic machine. Now the problem of whether the machine accepts is the same as the problem of whether there exists a path from the start state to the accepting state.

Savitch's theorem In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function f\in\Omega(\log(n)), :\mathsf\left(f\lef ...

guarantees that the algorithm can be simulated in ''O''(log² ''n'') deterministic space. The same problem for undirected graphs is called ''undirected s-t connectivity'' and was shown to be L-complete by Omer Reingold. This research won him the 2005

Grace Murray Hopper Award The Grace Murray Hopper Award (named for computer pioneer RADM Grace Hopper) has been awarded by the Association for Computing Machinery (ACM) since 1971. The award goes to a computer professional who makes a single, significant technical or serv ...

. Undirected st-connectivity was previously known to be complete for the class SL, so Reingold's work showed that SL is the same class as L. On alternating graphs, the problem is P-complete .

References

* *{{citation , last = Immerman , first = Neil , authorlink = Neil Immerman , title = Descriptive Complexity , title-link = Descriptive Complexity , year = 1999 , publisher = Springer-Verlag , location = New York , isbn = 0-387-98600-6 Graph connectivity Directed graphs NL-complete problems