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

С другой стороны, на интервальных графах [20, 24] и круговых аркграфах [21] путевая ширина поддается вычислению за полиномиальное время. Возможно, самым популярным положительным результатом в вычислении путевой ширины является алгоритм сложности <math>O(n^2) \, </math> для вычисления путевой ширины планарных графов, предложенный Сеймуром и Томасом в [29]. В той же работе они приводят также алгоритм сложности <math>O(n^4) \, </math> для вычисления оптимальной декомпозиции в форме ветвления. (Время исполнения этого алгоритма было улучшено до <math>O(n^3) \, </math> в [18]). Алгоритм из [29] по существу представляет собой алгоритм для параметра, называемого разрезной шириной и связанного с маршрутизацией телефонных звонков. Значение путевой ширины планарного графа составляет половину значения разрезной ширины его медиального графа.

Дорн [9] использует подход с матричным умножением в динамическом программировании для оценки констант c для различных задач. К примеру, в задаче нахождения [[максимальное независимое множество|максимального независимого множества]] <math>c \le \omega/2</math>, где <math>\omega </math> < 2.376 представляет собой экспоненту матричного умножения над кольцом, из чего следует, что эта задача на планарных графах разрешима за время <math>O(2^{2.52 \sqrt{n}})</math>. В задаче нахождения [[минимальное доминирующее множество|минимального доминирующего множества]] имеем <math>c \le 4 \,</math>, что дает время работы метода декомпозиции в форме ветвления <math>O(2^{3.99 \sqrt{n}})</math>. Представляется, что алгоритмы с временем исполнения <math>2^{O( \sqrt{n})}</math> могут быть построены даже для некоторых «нелокальных» задач – таких как нахождение [[гамильтонов цикл|гамильтонова цикла]], [[связное доминирующее множество|связного доминирующего множества]] и [[минимальное дерево Штейнера|минимального дерева Штейнера]], для которых нет известных алгоритмов для графов общего вида с путевой шириной <math>\ell \, </math>, имеющих время исполнения <math>2^{O( \ell)} \cdot n^{O(1)}</math> [11]. В этом случае необходимы специальные свойства некоторых оптимальных декомпозиций планарных графов в форме ветвления; грубо говоря, должно иметь место следующее: каждое ребро T соответствует диску на плоскости, такому, что все ребра G, соответствующие одному компоненту T — e, находятся внутри диска, а все остальные ребра – снаружи. Некоторые субэкспоненциальные алгоритмы на планарных графах могут быть обобщены для графов, вложенных на поверхности [10] и, далее, для классов графов, замкнутых относительно операции взятия минора [8].

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