Treewidth et le problème NL vs L

31

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 L.stg(V,E)NLL

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(bûche2n)

Shiva Kintali
la source

Réponses:

25

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]:Caroline du Nord1

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φ(X)Xst{(g,s,t) | tw(g)k, il y a un chemin de s à t dans 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)

Michael Blondin
la source