Treewidth und das NL vs L Problem

31

Die ST-Konnektivität ist das Problem, zu bestimmen, ob in einem gerichteten Graphen ein gerichteter Pfad zwischen zwei getrennten Eckpunkten und . Ob dieses Problem im Logspace gelöst werden kann, ist ein seit langem offenes Problem. Dies nennt man das vs Problem.stG(V,E)NLL

Was ist die Komplexität von ST-Connectivity, wenn der zugrunde liegende ungerichtete Graph von die Baumbreite begrenzt hat?G

Ist es bekannt, dass es NL-schwer ist? Gibt es eine obere Grenze für ?o(log2n)

Shiva Kintali
quelle

Antworten:

25

Es scheint, dass das Problem in L von [EJT10] und somit in L-Vervollständigung unter von [CM87] vorliegt. Siehe Seite 2 von [EJT10]:NC1

Die Anwendung von Satz I.3 auf die Formel ausdrückt, dass ein einfacher Weg von nach zeigt, dass das Problem liegt in Lϕ(X)Xst{(G,s,t) | tw(G)k, there is a path from s to t in G}

Tatsächlich gilt dieses Ergebnis für alle Probleme in Graphen mit begrenzter Breite, die in der monadischen Logik zweiter Ordnung in L formuliert werden können.

[EJT10] Michael Elberfeld, Andreas Jakoby und Till Tantau. Logspace-Versionen der Sätze von Bodlaender und Courcelle. In Proceedings of the 51. Annual Symposium on Foundations of Computer Science (FOCS), Seiten 143–152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: Komplette Probleme für den deterministischen logarithmischen Raum. J. Algorithms 8 (3): 385 & ndash; 394 (1987)

Michael Blondin
quelle