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 directed graph D (D = (V, A)), the reachability relation is the transitive closure of it's arc set A. In other words, 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.

Typically algorithms for reachability that require preprocessing (and their corresponding data structures) are called oracles (similarly there are oracles for distance and approximate distance queries).

Node failures

An interesting 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