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

, 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 on a set of input values. An example of a decision problem is deciding whether a given natura ...

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 theoretical 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 ...

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 al ...

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...

. 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 (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

of problems that can be solved by a

non-deterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

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 In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory s ...

, that is, every problem in the class NL is reducible to connectivity under a

log-space reduction In computational complexity theory, a log-space reduction is a reduction (complexity), reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of Pointer (computer progr ...

. This remains true for the stronger case of

first-order reduction In computer science, a first-order reduction is a very strong type of reduction between two computational problems in computational complexity theory. A first-order reduction is a reduction where each component is restricted to be in the class FO ...

s . 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 space-constructable function f\in\Omega(\log(n)) ...

guarantees that the algorithm can be simulated in ''O''(log² ''n'') deterministic space. The same problem for

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

s is called ''undirected s-t connectivity'' and was shown to be in L by

Omer Reingold Omer Reingold () is an Israeli computer scientist. He is the Rajeev Motwani professor of computer science in the Computer Science Department at Stanford University and the director of thSimons Collaboration on the Theory of Algorithmic Fairness ...

. 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