nonreachability

Nonreachability is a concept used in graph theory, computer networks, and formal analysis to describe the absence of a path from a given source to a target within a directed structure. More precisely, in a directed graph G = (V, E), a node v is reachable from a node u if there exists a directed path from u to v. If no such path exists, v is nonreachable from u. The term is typically understood relative to a specified source node and does not imply a global property of the graph.

Formally, reachability forms a relation on V, and nonreachability is the complement of this relation. Nonreachability is asymmetric in directed graphs: it is possible for v to be nonreachable from u but for u to be nonreachable from v. In undirected graphs, nonreachability coincides with disconnection, but in directed graphs it reflects directionality.

Computationally, nonreachability is determined by performing a graph traversal from the chosen source (such as breadth-first or depth-first search) and identifying the vertices that are not discovered. The set of nonreachable vertices consists of those not encountered during the traversal. The problem of checking reachability (and thus nonreachability) is solvable in linear time in the size of the graph, O(n + m), for finite graphs.

Applications of nonreachability include network design and diagnostics (identifying partitions or routing failures), access control (ensuring certain states are unattainable), and program or model checking (proving that unsafe states are nonreachable from initial states). Edge cases arise in infinite or dynamic graphs, where reachability properties may require more sophisticated methods.