st-connectivity

In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s. Formally, the decision problem is given by On a sequential computer, st-connectivity can easily be solved in linear time by either depth-first search or breadth-first search.

For instance, the complexity class 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.

This remains true for the stronger case of first-order reductions (Immerman 1999, p. 51).

Savitch's theorem guarantees that the algorithm can be simulated in O(log2 n) deterministic space.

There is a path directed from "s" to "t" in the first graph, but not in the second.