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.

Relevant topics on
Graph connectivity

Formally, the decision problem is given by

PATH = {⟨D, s, t⟩ | D is a directed graph with a path from vertex s to t}.

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 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 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). 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 guarantees that the algorithm can be simulated in O(log2 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. 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 (Immerman 1999, p. 54).

gollark: Did you know? [C++] is, by definition, better than C,[1] but most people are too feeble-minded to learn it, and usually die of an aneurism when they begin to learn how to use templates.[citation needed] Given the complexity of the language, only the best programmers can actually use it, and because of the necessary skills, the programs are always smaller, faster, and better than programs written in other languages.
gollark: Surely you could just have your code scan the entire contents of memory via ctypes every minute or so?
gollark: https://i.redd.it/x9dttazcllp81.jpg
gollark: That is LyricLy.
gollark: https://github.com/mTvare6/hello-world.rs

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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.