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 ?

up vote 25 down vote accepted

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)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.