Treewidth и проблема NL против L

31

ST-связность - это проблема определения, существует ли направленный путь между двумя выделенными вершинами и в ориентированном графе . Может ли эта проблема быть решена в пространстве журналов, является давней открытой проблемой. Это называется проблемой противstG(V,E)NLL

В чем сложность ST-связности, когда базовый неориентированный граф имеет ограниченную ширину дерева.G

Известно ли, что это NL-hard? Есть верхняя граница известна?o(log2n)

Шива Кинтали
источник

Ответы:

25

Похоже, проблема в L в [EJT10] и, таким образом, L-полная в сводимость в [CM87]. Смотрите страницу 2 [EJT10]:NC1

Применение теоремы I.3 к формуле выражающей, что - простой путь от до показывает, что задача лежит в Lϕ(X)Xst{(G,s,t) | tw(G)k, there is a path from s to t in G}

На самом деле этот результат применим ко всем задачам на ограниченных графах ширины деревьев, которые можно сформулировать в монадической логике второго порядка в L.

[EJT10] Майкл Элберфельд, Андреас Якоби и Тилль Тантау. Варианты логических пространств теорем Bodlaender и Courcelle. В материалах 51-го ежегодного симпозиума по основам информатики (FOCS), стр. 143–152, 2010.

[CM87] Стивен А. Кук, Пьер МакКензи: Задачи, полные для детерминированного логарифмического пространства. J. Алгоритмы 8 (3): 385-394 (1987)

Майкл Блондин
источник