4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
Вычисление путевой ширины представляет собой NP-полную задачу ([29]). Более того, задача является NP-полной, даже если мы ограничим ее входные графы классом расщепляемых графов или двудольных графов [20]. | Вычисление путевой ширины представляет собой NP-полную задачу ([29]). Более того, задача является NP-полной, даже если мы ограничим ее входные графы классом расщепляемых графов или двудольных графов [20]. | ||
С другой стороны, на интервальных графах [20, 24] и круговых аркграфах [21] путевая ширина поддается вычислению за полиномиальное время. Возможно, самым популярным положительным результатом в вычислении путевой ширины является алгоритм сложности O( | |||
Алгоритм для планарных графов [29] может использоваться для построения приближенного алгоритма вычисления путевой ширины некоторых непланарных графов. На классах графов, исключающих граф с однократным пересечением в качестве минора, путевая ширина может быть аппроксимирована с коэффициентом 2.25 [7] (граф H является минором графа G, если H может быть получен из подграфа G после применения процедуры сжатия дуг). Наконец, из работы [13] следует, что для любого класса графов, замкнутых относительно операции взятия минора, может быть выполнена аппроксимация путевой ширины с постоянным коэффициентом. | С другой стороны, на интервальных графах [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; обозначим это множество графов за Bk. Проверить, содержит ли граф G фиксированный граф в качестве минора, можно за полиномиальное время [27]. Таким образом, из знания Bk следует возможность построения полиномиального по времени алгоритма для выяснения верности соотношения branchwidth(G) < k для любого фиксированного k. К сожалению, Bk известно только для небольших значений k; в частности, B0 = fP2g;B1 = fP4;K3g;B2 = fK4g, а B3 = fK5; V8; M6; Q3g (здесь Kr – это клика из r вершин; Pr – путь из r дуг; V8 – граф, получаемый из контура с 8 вершинами, если соединить все пары вершин с расстоянием в контуре, равным 4; M6 – октаэдр; а Q3 – трехмерный куб). Однако для любого фиксированного k можно построить линейный относительно n = jV(G)j алгоритм, который определяет, выполняется ли для входного графа G соотношение branchwidth(G) < k и, в случае положительного ответа, выдает соответствующую декомпозицию в форме ветвления [3]. Технически из этого следует, что нахождение ответа на вопрос, верно ли для конкретного графа G соотношение branchwidth(G) < k, в отношении параметра k является FPT-сложной задачей (иначе говоря, принадлежит к параметризованному классу сложности FPT). Более детальные сведения о параметризованных алгоритмах и классах сложности можно найти в [12]. Алгоритм, приведенный в статье [3], довольно сложен и использует технику характеристических последовательностей, которая также применялась для доказательства аналогичного результата в случае древесной ширины. Для конкретных случаев в k < 3 существуют более простые алгоритмы, использующие технику «правило редукции» [4]. Следует понимать, что B4 остается неизвестным, несмотря на то, что некоторые его элементы уже были обнаружены (включая графы додекаэдра и икосаэдра). Существует несколько алгоритмов, которые для заданного k могут за время 2O(k) • nO(1) либо определить верность утверждения о том, что путевая ширина данного графа G составляет не менее k, либо построить декомпозицию в форме ветвления ширины O(k) ([26]). Эти результаты можно обобщить, чтобы вычислить путевую ширину матроидов и даже более общие параметры. | Сжатие дуги или ее удаление не может привести к повышению путевой ширины. Согласно теории о минорах графов, из этого следует, что для любого фиксированного k существует конечное число минимальных относительно миноров графов, путевая ширина которых превышает k; обозначим это множество графов за Bk. Проверить, содержит ли граф G фиксированный граф в качестве минора, можно за полиномиальное время [27]. Таким образом, из знания Bk следует возможность построения полиномиального по времени алгоритма для выяснения верности соотношения branchwidth(G) < k для любого фиксированного k. К сожалению, Bk известно только для небольших значений k; в частности, B0 = fP2g;B1 = fP4;K3g;B2 = fK4g, а B3 = fK5; V8; M6; Q3g (здесь Kr – это клика из r вершин; Pr – путь из r дуг; V8 – граф, получаемый из контура с 8 вершинами, если соединить все пары вершин с расстоянием в контуре, равным 4; M6 – октаэдр; а Q3 – трехмерный куб). Однако для любого фиксированного k можно построить линейный относительно n = jV(G)j алгоритм, который определяет, выполняется ли для входного графа G соотношение branchwidth(G) < k и, в случае положительного ответа, выдает соответствующую декомпозицию в форме ветвления [3]. Технически из этого следует, что нахождение ответа на вопрос, верно ли для конкретного графа G соотношение branchwidth(G) < k, в отношении параметра k является FPT-сложной задачей (иначе говоря, принадлежит к параметризованному классу сложности FPT). Более детальные сведения о параметризованных алгоритмах и классах сложности можно найти в [12]. Алгоритм, приведенный в статье [3], довольно сложен и использует технику характеристических последовательностей, которая также применялась для доказательства аналогичного результата в случае древесной ширины. Для конкретных случаев в k < 3 существуют более простые алгоритмы, использующие технику «правило редукции» [4]. Следует понимать, что B4 остается неизвестным, несмотря на то, что некоторые его элементы уже были обнаружены (включая графы додекаэдра и икосаэдра). Существует несколько алгоритмов, которые для заданного k могут за время 2O(k) • nO(1) либо определить верность утверждения о том, что путевая ширина данного графа G составляет не менее k, либо построить декомпозицию в форме ветвления ширины O(k) ([26]). Эти результаты можно обобщить, чтобы вычислить путевую ширину матроидов и даже более общие параметры. | ||