Source Link
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 ?