<p>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]:</p>

<blockquote>
  <p>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</p>
</blockquote>

<p>Actually this result applies to all problems on bounded treewidth graphs which can be formulated in monadic second-order logic in L.</p>

<p>[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.</p>

<p>[CM87] Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394 (1987)</p>

CC BY-SA 3.0
2012-03-02T00:44:33.977Z
2012-03-02T22:07:33.743Z
2012-03-02T22:07:33.743Z
Michael Blondin
<p>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.</p>

<blockquote>
  <p>What is the complexity of ST-Connectivity, when the underlying undirected graph of $G$ has bounded treewidth.</p>
</blockquote>

<p>Is it known to be NL-hard ? Is there a $o({\log}^2n)$ upper bound known ?</p>

<cc.complexity-theory><graph-theory><space-bounded><treewidth><logspace>
Treewidth and the NL vs L Problem
Shiva Kintali
# Treewidth and the NL vs L Problem

(Asked by: username_0 on 2012-03-01)

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 ?

**Tags:** cc.complexity-theory, graph-theory, space-bounded, treewidth, logspace


---

## 1 answers

### Answer by username_1 on 2012-03-02. Score: 25 | Accepted answer

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)


---

