ST-connectivity
Encyclopedia
In computer science
and computational complexity theory
, 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
, 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 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 . 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 is complete for the class SL
under log-space reductions. Recently, Omer Reingold
won the Grace Murray Hopper Award
in 2005 for discovering a deterministic log-space undirected st-connectivity algorithm, which shows that SL is equal to L
. On alternating graphs, the problem is complete for P
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, st-connectivity or STCON is a decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
asking, for vertices s and t in a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
, if t is reachable
Reachability
In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...
from s.
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 NLNL (complexity)
In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space....
, as a non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
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 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
NL-complete
In computational complexity theory, NL-Complete is a complexity class which is complete for NL. It contains the most "difficult" or "expressive" problems in NL...
, that is, every problem in the class NL is reducible to connectivity under a log-space reduction
Log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers...
. 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
Savitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
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 is complete for the class SL
SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...
under log-space reductions. Recently, Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
won the Grace Murray Hopper Award
Grace Murray Hopper Award
The original Grace Murray Hopper Awards have been awarded by the Association for Computing Machinery since 1971. The award goes to a young computer professional who makes a single, significant technical or service contribution.-Recipients:* 1971 Donald E. Knuth* 1972 Paul H. Dirksen* 1972 Paul H...
in 2005 for discovering a deterministic log-space undirected st-connectivity algorithm, which shows that SL is equal to L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
. On alternating graphs, the problem is complete for P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
.