reachability

Reachability is the property that a particular state, node, or location can be reached from a given starting point under a specified set of rules. It is a fundamental concept in several fields, including graph theory, computer science, control theory, networking, and formal verification. In graphs, reachability concerns whether there exists a path from one node to another.

In graph theory and computer science, reachability is typically studied on directed or undirected graphs. The basic problem asks if a path exists from source s to target t. If a path exists for all pairs, the graph is strongly connected (directed) or connected (undirected). In directed graphs, reachability relations induce partial orders and transitive closures.

Algorithms for reachability include breadth-first search and depth-first search, which determine whether t is reachable from s in time linear in the size of the graph. Transitive closure computes reachability for all node pairs, using methods such as Floyd-Warshall, repeated BFS, or matrix-based approaches.

In control theory, reachability (often called controllability) refers to the ability to drive a system’s state to any desired value within finite time using admissible inputs. For linear time-invariant systems, the Kalman rank condition characterizes reachability via the controllability matrix.

In formal verification and model checking, reachability analysis explores the state space generated by system transitions to verify properties such as safety. Applications include path planning, routing, network resilience, and program correctness. Practical limits include state-space explosion and computational complexity on large or constrained systems.