Erreichbarkeitsproblem in Graphen

Das Erreichbarkeitsproblem in Graphen (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten ${\displaystyle s}$ zu einem Knoten ${\displaystyle t}$ gibt. Existiert solch ein Weg, so ist ${\displaystyle t}$ von ${\displaystyle s}$ aus erreichbar. Andernfalls ist ${\displaystyle t}$ von ${\displaystyle s}$ aus nicht erreichbar. GAP steht für engl. Graph Accessibility Problem und REACH für engl. Reachability.

• Die Abkürzung STCON steht für engl. s-t-Connectivity und bezeichnet das Erreichbarkeitsproblem in einem gerichteten Graphen. In dieser Variante ist es ein NL-vollständiges Problem.
• Die Abkürzung USTCON steht für engl. undirected s-t-Connectivity und bezeichnet das Erreichbarkeitsproblem in einem ungerichteten Graphen. In dieser Variante ist es ein L-komplexes Problem.

Es lässt sich beispielsweise mit Hilfe der Breitensuche oder der Tiefensuche lösen.