Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$ on undirected graphs is and whether any hardness results for $PATH$ on undirected graphs are known?
1 Answer
$\begingroup$
$\endgroup$
The undirected version of PATH, usually known as USTCON, is in L due to Reingold's theorem.
USTCON is trivially complete for L with respect to logspace reductions. I don't know if it is L-complete with respect to weaker reductions such as $\mathsf{AC}^0$ reductions; see this question.