# Treewidth and the NL vs L Problem

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