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

Пусть G – граф с n вершинами. ''[[Декомпозиция]] в форме ветвления'' применительно к графу G представляет собой пару <math>(T, \tau \, )</math>, где T – это дерево с вершинами, имеющими степень 1 или 3, а <math>\tau \, </math> – [[биекция]] множества листьев T на дуги G. [[Порядок]] дуги e в T, обозначаемый <math>\alpha (e)\, </math>, представляет собой число вершин v графа G, таких, что существуют листья <math>t_1</math>, <math>t_2</math> дерева T в различных компонентах T(V(T), E(T) — e) с <math>\tau (t_1)\, </math> и <math>\tau (t_2)\, </math>, у которых v является конечной точкой.

[[Ширина]] <math>(T, \tau )\, </math> равна <math>max_{e \in E(T)}</math>{<math>\alpha (e) \, </math>} – иначе говоря, максимальному порядку среди всех дуг T. ''Путевой шириной'' G является минимальная ширина среди всех декомпозиций G в форме ветвления (в случае, если <math>\mid E(G)\mid \le 1</math>, мы устанавливаем, что путевая ширина равна 0; если <math>\mid E(G)\mid = 0</math>, то G не допускает декомпозиции в форме ветвления; если <math>\mid E(G)\mid = 1</math>, то у G имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой).

Вышеприведенное определение может быть напрямую расширено на [[гиперграф|гиперграфы]], в которых <math>\tau \, </math> представляет собой биекцию листьев T на гипердуги G. Это же определение можно так же легко распространить на [[матроид|матроиды]].

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

Алгоритм для планарных графов [29] может использоваться для построения приближенного алгоритма вычисления путевой ширины некоторых непланарных графов. На классах графов, исключающих граф с однократным пересечением в качестве минора, путевая ширина может быть аппроксимирована с коэффициентом 2.25 [7] (граф H является [[минор|минором]] графа G, если H может быть получен из подграфа G после применения процедуры сжатия дуг). Наконец, из работы [13] следует, что для любого класса графов, замкнутых относительно операции взятия минора, может быть выполнена аппроксимация путевой ширины с постоянным коэффициентом.

Сжатие дуги или ее удаление не может привести к повышению путевой ширины. Согласно теории о минорах графов, из этого следует, что для любого фиксированного k существует конечное число минимальных относительно миноров графов, путевая ширина которых превышает k; обозначим это множество графов за <math>\mathfrak{B}_k</math>. Проверить, содержит ли граф G фиксированный граф в качестве минора, можно за полиномиальное время [27]. Таким образом, из знания <math>\mathfrak{B}_k</math> следует возможность построения полиномиального по времени алгоритма для выяснения верности соотношения <math>branchwidth(G) \le k </math> для любого фиксированного k. К сожалению, <math>\mathfrak{B}_k</math> известно только для небольших значений k; в частности, <math>\mathfrak{B}_0 = \big\{ P_2 \big\} </math>}; <math>\mathfrak{B}_1 = \big\{ P_4 , K_3 \big\} </math>; <math>\mathfrak{B}_2 = \big\{ K_4 \big\} </math>, а <math>\mathfrak{B}_3 = \big\{ K_5; V_8; M_6; Q_3 \big\} </math> (здесь <math>K_r \, </math> – это клика из r вершин; <math>P_r \, </math> – путь из r дуг; <math>V_8 \, </math> – граф, получаемый из контура с 8 вершинами, если соединить все пары вершин с расстоянием в контуре, равным 4; <math>M_6 \, </math> – октаэдр; а <math>Q_3 \, </math> – трехмерный куб). Однако для любого фиксированного k можно построить линейный относительно <math>n = |V(G)| \, </math> алгоритм, который определяет, выполняется ли для входного графа G соотношение <math>branchwidth(G) \le k </math> и, в случае положительного ответа, выдает соответствующую декомпозицию в форме ветвления [3]. Технически из этого следует, что нахождение ответа на вопрос, верно ли для конкретного графа G соотношение <math>branchwidth(G) \le k </math>, в отношении параметра k является FPT-сложной задачей (иначе говоря, принадлежит к параметризованному [[класс сложности|классу сложности]] FPT). Более детальные сведения о параметризованных алгоритмах и классах сложности можно найти в [12]. Алгоритм, приведенный в статье [3], довольно сложен и использует технику характеристических последовательностей, которая также применялась для доказательства аналогичного результата в случае древесной ширины. Для конкретных случаев с <math>k \le 3 \, </math> существуют более простые алгоритмы, использующие технику «правило редукции» [4]. Следует понимать, что <math>\mathfrak{B}_4</math> остается неизвестным, несмотря на то, что некоторые его элементы уже были обнаружены (включая графы додекаэдра и икосаэдра). Существует несколько алгоритмов, которые для заданного k могут за время <math>2^{O(k)} \cdot n^{O(1)}</math> либо определить верность утверждения о том, что путевая ширина данного графа G составляет не менее k, либо построить декомпозицию в форме ветвления ширины O(k) ([26]). Эти результаты можно обобщить, чтобы вычислить путевую ширину матроидов и даже более общие параметры.

В отличие от древесной ширины, максимальные по количеству дуг графы заданной путевой ширины не так легко поддаются характеризации (в случае древесной ширины они представляют собой просто k-деревья, то есть хордальные графы, все максимальные клики которых имеют размер k + 1). Алгоритм генерации таких графов, приведенный в [23], выявляет несколько структурных задач, связанных с этим параметром.

Дорн [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]. Параметризованные алгоритмы, основанные на декомпозиции в форме ветвления, могут быть обобщены с планарных графов на графы, вложенные в поверхности, и далее на графы, исключающие фиксированный граф в качестве минора.

* ''[[Древесная ширина графов]]

22. Paul, C., Proskurowski, A., Telle, J.A.: Generating graphs of bounded branchwidth. In: Proceedings of the 32nd Workshop on Graph Theoretic Concepts in Computer Science (WG 2006). Lecture Notes Computer Science, vol. 4271, pp. 205-216. Springer, Berlin (2006)

23. Paul, C., Telle, J.A.: New tools and simpler algorithms for branchwidth. In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), 2005 pp. 379-390

24. Robertson, N. Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition J. Combin. Theor. Ser. B 52, 153-190 (1991)

25. Robertson, N. Seymour, P.D.: Graph minors. XII. Distance on a surface. J. Combin.Theor. Ser. B 64, 240-272 (1995)

26. Robertson, N. Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Combin.Theor. Ser. B 63,65-110 (1995)

27. Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. J. Combin. Theor. Ser. B 62, 323-348 (1994)

28. Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14,217-241 (1994)