Reichbarkeit

Reichbarkeit, literally meaning "reachability" in German, is a fundamental concept in graph theory and computer science that describes whether there is a path from one vertex to another within a directed or undirected graph. In a directed graph (digraph), a vertex v is reachable from a vertex u if there exists a sequence of directed edges that leads from u to v. When the graph is undirected, reachability simply means that any two vertices lie in the same connected component.

The question of reachability can be formalized as: given a graph G = (V, E) and two vertices s, t ∈ V, does there exist a walk from s to t? This decision problem is solved efficiently by traversal algorithms such as depth‑first search (DFS) and breadth‑first search (BFS). For directed graphs, the reverse reachable set of a vertex u – all vertices that can reach u – can be found by running DFS on the transpose of the graph. The transitive closure of a digraph, which records reachability for all vertex pairs, can be computed in quadratic time with Floyd‑Warshall or in linear time per source with repeated BFS or DFS.

Reachability is also used in databases (for query optimization), in automata theory (for state reachability in finite state machines), in network reliability (checking connectivity), and in formal verification (model checking). In the context of graph classes, a digraph is strongly connected if every vertex is reachable from every other vertex, whereas a weakly connected digraph becomes connected when all edge directions are ignored.

In complexity theory, the reachability problem for directed acyclic graphs (DAGs) is NL‑complete, meaning it belongs to the class of problems solvable in nondeterministic logarithmic space. The problem remains NL‑complete for general directed graphs as well, but if the graph is represented by an adjacency matrix, reachability can be decided in polynomial time. The notion of reachability is central to many algorithms that need to determine connectivity or to perform reachability queries over massive graphs, where specialized data structures like reachability indexes are employed.