Treewidth y el problema NL vs L

ST-conectividad es el problema de determinar si existe un camino dirigido entre dos vértices distinguidos y t en un gráfico dirigido G ( V , E ) . Si este problema se puede resolver en el espacio de registro, es un problema abierto de larga data. Esto se llama el N L vs L problema.$s$$t$$G(V,E)$$NL$$L$

¿Cuál es la complejidad de la conectividad ST, cuando el gráfico subyacente no dirigido de tiene un ancho de árbol acotado?$G$

¿Se sabe que es NL-hard? ¿Se conoce un límite superior ?$o({\log}^2n)$

Parece que el problema está en L por [EJT10] y, por lo tanto, L-completo bajo reducibilidad por [CM87]. Consulte la página 2 de [EJT10]:$\text{NC}^1$

La aplicación del teorema I.3 a la fórmula que expresa que X es una ruta simple de s a t muestra que el problema { ( G , s , t ) |  tw ( G ) ≤ k , hay una ruta de  s  a  t  en  G } se encuentra en 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 realidad, este resultado se aplica a todos los problemas en los gráficos de ancho de árbol acotado que pueden formularse en lógica monádica de segundo orden en L.

[EJT10] Michael Elberfeld, Andreas Jakoby y Till Tantau. Versiones de espacio de registro de los teoremas de Bodlaender y Courcelle. En Actas del 51º Simposio anual sobre fundamentos de la informática (FOCS), páginas 143–152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: problemas completos para el espacio logarítmico determinista. J. Algoritmos 8 (3): 385-394 (1987)