retagging the question
Shiva Kintali
• 10.5k
• 37
• 74

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 ?