Reachability

In graph theory, reachability is the ability 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 directed graph D = (V, A), the reachability relation of D is the transitive closure of its arc set A, which is to say the set of all ordered pairs (s, t) of vertices in V for which there exist vertices v₀ = s, v₁, …, v_d = t such that (v_{i - 1}, v_i ) is in A for all 1 ≤ i ≤ d.

DAGs and partial orders

The reachability relation of a directed acyclic graph is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction. If a directed graph is not acyclic, its reachability relation will be a preorder but not a partial order.

Algorithms

Algorithms for reachability fall into two classes: those that require preprocessing and those that do not. For the latter case, resolving a single reachability query can be done in linear time using algorithms such as breadth first search or iterative deepening depth-first search.

Preprocessing algorithms such as a simplified Floyd–Warshall algorithm compute all pairwise reachabilities, so that reachability queries can then be answered immediately. Algorithms that precompute all the answers (or the data structures containing the answers) are sometimes called oracles, since the precomputed reachability matrix then allows queries to be answered in a single instruction. (Such oracles also exist for distance and approximate distance queries.)

Node failures

A related problem is to solve reachability queries with some number k of node failures. For example: "Can node u still reach node v even though nodes s₁, ..., s_k have failed and can no longer be used?" The breadth-first search technique works just as well on such queries, but constructing an efficient oracle is more challenging.

See also

• st-connectivity
• Petri net