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

Теорема 1 (Арнборг и др. [1]). Пусть даны граф G и целое число k. Задача определения того факта, что древесная ширина графа G не превышает k, является недетерминированной и имеет полиномиальное время выполнения (является NP-полной).

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

Теорема 2 (Бодлендер [4]). Для каждого фиксированного значения k существует алгоритм, который для заданного графа G = (V, E) и целочисленного k может определить, верно ли, что древесная ширина G не превышает k, и в случае положительного ответа предложить древесную декомпозицию G с шириной не более k за время O(n).

Для поиска древесной ширины часто используются две эвристики – минимального заполнения и минимальной степени. При применении эвристики минимальной степени выбирается вершина v с минимальной степенью. Граф G0 строится в результате превращения окрестности вершины v в клику и последующего удаления вершины v и инцидентных ей дуг. Хордальный суперграф H0 графа G0 вычисляется рекурсивным образом при помощи эвристики. Затем строится хордальный суперграф H графа G в результате добавления вершины v и инцидентных ей дуг из G в H0. Эвристика минимального заполнения работает сходным образом, однако в данном случае выбирается такая вершина v, чтобы количество ребер, добавляемых для превращения ее окрестности в клику, было минимально возможным.

Теорема 3 (Фомин и др. [9]). Существует алгоритм, который для данного графа G = (V, E) определяет его древесную ширину и находит его древесную декомпозицию минимальной ширины за время O(1:8899n).