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.

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

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