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

Дорн [9] использует подход с матричным умножением в динамическом программировании для оценки констант c для различных задач. К примеру, в задаче нахождения максимального независимого множества c < !/2, где ! < 2:376 представляет собой матричное умножение над кольцом, из чего следует, что эта задача на планарных графах разрешима за время O(22:52pn). В задаче нахождения минимального доминирующего множества имеем c < 4, что дает время работы метода декомпозиции в форме ветвления O(23:99 n). Представляется, что алгоритмы с временем исполнения 2°^"' могут быть построены даже для некоторых «нелокальных» задач – таких как нахождение гамильтонова цикла, связного доминирующего множества и минимального дерева Штейнера, для которых нет известных алгоритмов для графов общего вида с путевой шириной I, имеющих время исполнения 20{V> ■ nO(1) [11]. В этом случае необходимы специальные свойства некоторых оптимальных декомпозиций планарных графов в форме ветвления; грубо говоря, должно иметь место следующее: каждая дуга T соответствует диску на плоскости, такому, что все дуги G, соответствующие одному компоненту T — e, находятся внутри диска, а все остальные дуги – снаружи. Некоторые субэкспоненциальные алгоритмы на планарных графах могут быть обобщены для графов, вложенных на поверхности [10] и, далее, для классов графов, замкнутых относительно операции взятия минора [8].

Подобный же подход может использоваться для параметризованных задач на планарных графах. К примеру, параметризованный алгоритм для нахождения доминирующего множества размера меньше k (или сообщения о том, что такого множества не существует) за время 2O(k)nO(1) может быть найден благодаря следующим наблюдениям: существует константа c, такая, что любой планарный граф, имеющий путевую ширину не менее cpk, не содержит доминирующего множества с размером не более k. Тогда для данного k алгоритм вычисляет оптимальную декомпозицию в форме ветвления для планарного графа G, и если его ширина превышает cpk, делает вывод, что у G не имется доминирующего множества размера k. В ином случае оптимальное доминирующее множество вычисляется при помощи алгоритма динамического программирования за время 2O(k)nO(1). Имеется несколько способов ограничения параметра планарного графа в терминах его путевой или древесной ширины, включая техники, сходные с подходом Бэйкер к алгоритмам аппроксимации [1], использование сепараторов либо некоторые комбинаторные методы, представленные в [16]. Другой обобщенный подход к ограничению путевой ширины планарного графа параметрами основан на исследованиях Робертсона и коллег [28], относящихся к быстрому исключению планарного графа, что приводит нас к понятию двумерности [6]. Параметризованные алгоритмы, основанные на декомпозиции в форме ветвления, могут быть обобщены с планарных графов на графы, вложенные в поверхности, и далее на графы, исключающие фиксированный граф в качестве минора.