ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in logspace, is a long-standing open problem. This is called the $NL$ vs $L$ problem.
What is the complexity of ST-Connectivity, when the underlying undirected graph of $G$ has bounded treewidth.
Is it known to be NL-hard ? Is there a $o({\log}^2n)$ upper bound known ?
It appears the problem is in L by [EJT10] and thus L-complete under $\text{NC}^1$ reducibility by [CM87]. See page 2 of [EJT10]:
Applying Theorem I.3 to the formula $\phi(X)$ expressing that $X$ is a simple path from $s$ to $t$ shows that the problem $\{(G,s,t) \text{ } | \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$ lies in L
Actually this result applies to all problems on bounded treewidth graphs which can be formulated in monadic second-order logic in L.
[EJT10] Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 143–152, 2010.
[CM87] Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394 (1987)
