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

Сжатие дуги или ее удаление не может привести к повышению путевой ширины. Согласно теории о минорах графов, из этого следует, что для любого фиксированного k существует конечное число минимальных относительно миноров графов, путевая ширина которых превышает k; обозначим это множество графов за <math>\mathfrak{B}_k</math>. Проверить, содержит ли граф G фиксированный граф в качестве минора, можно за полиномиальное время [27]. Таким образом, из знания <math>\mathfrak{B}_k</math> следует возможность построения полиномиального по времени алгоритма для выяснения верности соотношения branchwidth(G) < k для любого фиксированного 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 можно построить линейный относительно 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]). Эти результаты можно обобщить, чтобы вычислить путевую ширину матроидов и даже более общие параметры.