Путевая ширина графа: различия между версиями

1. Известно, что любой планарный граф G имеет путевую ширину не более p4:5 • pjV(G)j (или не более 2 3 y/\E(G)\ + 2) [17]. Возможно ли улучшить эту верхнюю границу? Любое возможное улучшение приведет к ускорению работы многих известных точных и параметризованных алгоритмов на планарных графах, использующих динамическое программирование или декомпозицию в форме ветвления.

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

3. Найти Bk для значений k больше 3. Единственный структурный результат Bk заключается в том, что его планарные элементы являются либо самодвойственными, либо попарно двойственными. Это заключение следует из того факта, что двойственные планарные графы имеют одинаковую путевую ширину [29, 16].

4. Найти точный алгоритм для вычисления путевой ширины сложности O*(2") (нотация O*() предполагает, что неэкспоненциальные члены классической нотации O() отбрасываются).

5. Зависимость линейного по времени алгоритма вычисления путевой ширины от k очень велика [3].  Найти алгоритм, состоящий из 2O(k) • nO(1) шагов, который определяет верность утверждения о том, что путевая ширина входного графа с n вершинами составляет не более k.