ST-connectivity
From Wikipedia, the free encyclopedia
- The correct title of this article is st-connectivity. The initial letter is shown capitalized due to technical restrictions.
st-connectivity (reachability) refers to a problem in computer science and computational complexity theory, a decision problem asking if two vertices s and t in a directed graph are connected by a path.
The language of the decision problem is given by PATH = {<D, s, t> | D is a directed graph with a path from vertex s to t}.
[edit] Complexity
The 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 which node is the node currently under consideration. The algorithm terminates if either the target node t is reached, or the path so far exceeds m, 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 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 (Immerman 1999, p. 51).
It is unknown whether connectivity is solvable in deterministic logspace, however Savitch's theorem guarantees that the algorithm can be simulated in log2n deterministic space.
The same problem for undirected graphs is called undirected s-t connectivity and is log-space complete for the class SL, recently shown to be equal to L.
[edit] References
- Sipser, Michael (2006). Introduction to the Theory of Computation. Thompson Course Technology. ISBN 0-534-95097-3.
- Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6.
