Treewidth et le problème NL vs L

La connectivité ST est le problème de déterminer s'il existe un chemin dirigé entre deux sommets distincts et t dans un graphe dirigé G ( V , E ) . La question de savoir si ce problème peut être résolu dans l'espace de journalisation est un problème ouvert de longue date. C'est ce qu'on appelle le problème N L vs $s$$t$$G(V,E)$$NL$$L$

Quelle est la complexité de ST-Connectivity, lorsque le graphe non orienté sous-jacent de a une largeur d'arbre limitée.$G$

Est-il connu pour être NL-difficile? Y a-t-il une limite supérieure connue?$o({\log}^2n)$

Il semble que le problème soit en L par [EJT10] et donc en L-complet sous réductibilité par [CM87]. Voir page 2 de [EJT10]:$\text{NC}^1$

L'application du théorème I.3 à la formule exprimant que X est un simple chemin de s à t montre que le problème { ( G , s , t ) |  tw ( G ) ≤ k , il existe un chemin de  s  à  t  dans  G } réside dans L$\phi(X)$$X$$s$$t$$\{(G,s,t) \text{ } | \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$

En fait, ce résultat s'applique à tous les problèmes sur les graphes à largeur d'arbre bornée qui peuvent être formulés dans une logique monadique de second ordre en L.

[EJT10] Michael Elberfeld, Andreas Jakoby et Till Tantau. Logspace versions des théorèmes de Bodlaender et Courcelle. Dans Actes du 51e Symposium annuel sur les fondements de l'informatique (FOCS), pages 143-152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: Problèmes complets pour l'espace logarithmique déterministe. J. Algorithms 8 (3): 385-394 (1987)