reachabilitywithouts

Reachabilitywithouts is a variant concept in graph theory and network analysis. Given a graph G = (V, E), a distinguished start vertex s ∈ V, and a forbidden set W ⊆ V, the reachability-withouts from s consists of all vertices v ∈ V that can be reached from s by a path that does not visit any vertex in W. By convention, s is considered reachable from itself unless s ∈ W, in which case the reachability is empty.

Formally, let G' be the subgraph of G obtained by removing all vertices in W (and incident edges). Then the reachability-withouts from s is the standard reachability set R_G'(s) in G'. In undirected graphs this coincides with ordinary reachability after removing W; in directed graphs it respects edge directions. A common algorithm is to run a BFS or DFS on G' starting from s. The time complexity is O(|V| + |E|) for each evaluation.

Variants include separating whether the start vertex s must be outside W; allowing multiple start vertices; considering path length constraints; and distinguishing vertex-avoidance (removing W) from edge-avoidance (forbidding specific edges). Reachabilitywithouts is related to vertex cuts, as a small W can drastically reduce reachable sets, and to standard reachability, since R(s) ⊆ V when W ≠ ∅. It also connects to reliability analysis and planning under constraints.

Applications appear in network routing with node failures, evacuation planning with blocked zones, and privacy-aware reachability queries where certain nodes must not be traversed. A simple example: in a graph with edges A→B, A→D, B→C, removing B yields the set {A, D} as reachables from A.