Graph reachability

Graph reachability is the problem of determining whether a directed path exists from a source vertex to a target vertex in a graph. It is one of the most fundamental problems in graph theory and algorithm design, serving as the abstract template for countless real-world questions: can a signal propagate through a network? Can a disease spread from one host to another? Can a proof be derived from given axioms?

The complexity of graph reachability depends critically on the representation. For explicitly given graphs, the problem is solvable in linear time and space via breadth-first or depth-first search. But when the graph is given implicitly — as the configuration graph of a Turing machine, for instance — reachability becomes the engine of complexity class separations. The Savitch's theorem proof relies on showing that implicit reachability in polynomially-large configuration graphs can be solved in polynomial space, collapsing NPSPACE to PSPACE.

Graph reachability is the skeleton key of computational complexity. Nearly every hardness result — from NP-completeness to PSPACE-completeness — is ultimately a reachability problem in disguise. The field's obsession with exotic problem classes has obscured this uncomfortable fact: if you understand reachability, you already understand most of what complexity theory has to say.