= ST-connectivity
{c}
{wiki}
= Directed graph reachability problem
{synonym}
The directed <ST-connectivity> problem asks whether a <directed graph> contains a <graph path> from specified <vertices> $s$ to $t$. A zero-length <graph path> is permitted, so $s=t$ is a positive instance. It is <NL-complete> under <logspace many-one reductions>.
For membership in <NL>, guess a <graph path> of at most $N-1$ <edges>, where $N$ is the number of <vertices>. Retain only the current <vertex> and a step counter. A reachable target has a simple <graph path> within that bound, and the stored indices use <logarithmic space>.
For hardness, take an <NL> machine on a fixed <input> and construct its <configuration graph>. Only polynomially many configurations are possible within the workspace bound, and all configurations and local transition <edges> can be enumerated with a <logspace transducer>. Add one target collecting the accepting configurations. The target is reachable from the initial configuration exactly when the original machine accepts. This translates any <NL> language into directed reachability while respecting the reduction's storage bound.
Back to article page
