Алгоритмы лог-пространства на графах с ограниченной шириной дерева

23

Ширина дерева показывает, насколько близок график к дереву. NP-трудно вычислить ширину дерева. Наиболее известный алгоритм приближения достигает O(logn) фактор.

Теорема Курселя гласит, что любое свойство графов, определяемых в монадической логике второго порядка (MSO2), может быть определено за линейное время на любом классе графов ограниченной ширины дерева . Недавняя работа показала, что теорема Курселя все еще остается в силе, когда «линейное время» заменяется на «логпространство». Однако это не решает пространственную сложность изоморфизма графов на графах с ограниченной шириной дерева. Самый известный результат помещает его в LogCFL.

Есть ли другие проблемы, которые:

  • NP-сложный (или неизвестный в P) на общих графах, и
  • известно, что разрешимо за линейное / полиномиальное время на графах с ограниченной шириной дерева, и
  • НЕ известно, чтобы быть в LogSpace?
Шива Кинтали
источник
Какой упоминается в факторе приближения? n
gphilip
- количество вершин во входном графе. n
Шива Кинтали
5
Мы можем, в общем, сделать лучше, чем в аппроксимирующей ширине дерева. Лучший из известных мне алгоритмов аппроксимации за полиномиальное время даетO(O(logn)коэффициент аппроксимации, гдеw- ширина графика. См. Feige, Hajiaghayi и Lee,Улучшенные алгоритмы аппроксимации для вершинных сепараторов минимального веса, STOC 2005.O(logw)w
gphilip

Ответы:

15

Полином Татте является примером.

Это обобщение хроматического полинома , которое само по себе является проблемой # P-hard в любой разумной формулировке. В

Оценка полинома Тутте для графов ограниченной ширины дерева , С. Д. Нобл, Комбинаторика, Вероятность и вычисления, 1998,

O(f(k)n4+ϵ)kn , где проблема сложности обсуждается в разделе 8.

Кажется, что проблема не может быть выражена непосредственно в MSO2, хотя я не знаком с подробными определениями ... Надеюсь, эта проблема - то, что вам нужно!

Сянь-Чжи Чан 張顯 之
источник
Что такое функция F?
Майкл Блондин
kO(2(k3+ϵ))
8
Маковски говорит, что «все полиномы графов, изученные в литературе, определены SOL», и дает формулировку полинома Тутте в терминах SOL, стр. 15 «От зоопарка к зоологии: на пути к общей теории полиномов графов». В «Алгоритмическом использовании теоремы Фефермана-Vaught» он расширяет теорему Курселя, чтобы показать возможность отслеживания для полиномов, определяемых SOL, на ограниченных графах ширины дерева.
Ярослав Булатов