Graph-Reachability Problem

computation

Definition

Graph-Reachability Problem

Given a graph $G=(V,E)$ and vertices $u,v\in V$. The graph reachability problem asks whether there exists a path from $u$ to $v$ in $G$.

The graph reachability problem is a decision problem.

Example

SIMPLE program for graph reachability

The following SIMPLE-style program computes the set of all vertices reachable from $u$ and then checks whether $v$ is among them.

S := {u};
repeat
    S' := S;
    for all i ∈ S' do {
        for all j ∈ V do {
            if (i,j) ∈ E then S := S ∪ {j};
        }
    }
until S = S';
if v ∈ S then return true;
else return false;

The set $S$ grows monotonically. When the loop stops, no new vertex can be added, so $S$ is exactly the set of vertices reachable from $u$.