The directed graph reachability problem asks whether a directed graph contains a directed path from a specified vertex to a specified vertex . It is NL-complete.
The configuration graph of a machine on a fixed input has one vertex for each machine configuration and a directed edge for each valid computation step.
Articles by others on the same topic
**St-connectivity** refers to a concept in graph theory, particularly in the context of directed and undirected graphs. It concerns whether there is a path between two specific vertices in a graph, typically denoted as vertex **S** and vertex **T**: 1. **In Undirected Graphs**: A graph is said to be **st-connected** if there exists a path between vertices **S** and **T**.