Какие графовые проблемы являются

10

После эквивалентных вопросов относительно NP-полноты (см. Вопрос о весе и заданный вопрос ) мне стало интересно, как эти атрибуты влияют на параметризованные проблемы.

  • Какие задачи жесткого графа являются -твердыми на ориентированных графах, но фиксированными параметрами, которые можно отследить на неориентированных графах?NпW[1]
  • Какие задачи жесткого графа являются -твердыми на взвешенных графах, но фиксированными параметрами, которые можно отследить на невзвешенных графах?NпW[1]

Итак, у нас есть проблемы, которые становятся сложнее в направленной версии. Как насчет весов? Могут ли они усложнить параметризованную проблему?

cc.complexity-theory graph-algorithms parameterized-complexity fixed-parameter-tractable RB
источник
Есть несколько случаев, которые не совсем совпадают и не известны. например, вычисление ширины дерева в неориентированных графах является fpt, ​​но вычисление направленной ширины дерева не известно, если это fpt. но в работе Джонсона Эталя есть приближение fpt 3.
Саид
2
Или другой случай, если мы играем в игру ширины DAG в неориентированных графах, мы получаем разложение дерева. Но ширина дерева вычислений - FPT, а ширина метки вычислений - PSPACE-полная .
Саид

Ответы:

9

Проблема непересекающихся путей: при заданных и k парах узлов существуют ли непересекающиеся пути узлов, соединяющие данные пары. Параметризован k , в FPT, когда G не направлен на основополагающую работу Робертсона и Сеймура. NP-Hard для k = 2, когда G направлен - из работы Fortune, Hopcroft and Wylie (1980).гККгКзнак равно2г

Чандра Чекури
источник
3

Вычисление ширины дерева и разложения дерева в неориентированных графах является параметром FPT по ширине. Многие меры ширины орграфа (или соответствующая им игра) эквивалентны ширине дерева в неориентированных графах. Точный класс сложности многих из них неизвестен, но недавно было показано, что DAG-Width является PSPACE-полной .

Saeed
источник