Декомпозиция графа в дерево

В предыдущих двух разделах мы видели, как конкретные NP-сложные задачи (а именно задачи о независимом множестве с максимальным весом и раскраске графа) могут решаться при ограниченной структуре входных данных.

Наши алгоритмы в обоих случаях использовали особенности конкретной разновидности структуры: тот факт, что входные данные можно было разбить на подзадачи с очень ограниченным взаимодействием.

Например, чтобы решить задачу о независимом множестве с максимальным весом для дерева, мы используем специальное свойство (корневых) деревьев: после принятия решения о том, должен ли узел u включаться в независимое множество или нет, подзадачи в каждом поддереве становятся полностью изолированными; мы можем решать каждую из них так, словно остальных не существует.

В обобщенных графах, где может не быть узла, «разрывающего связь» между подзадачами в других частях графа, такая удобная возможность отсутствует. В задаче о независимом множестве для обобщенного графа решения, принятые в одном месте, приводят к сложным вторичным эффектам по всему графу.

Итак, мы можем задать себе «ослабленную» версию нашего вопроса: насколько общим должен быть класс графов, чтобы для него можно было использовать концепцию «ограниченного взаимодействия» — рекурсивной фрагментации входных данных с использованием малых множеств узлов — для проектирования эффективных алгоритмов для таких задач, как задача о независимом множестве с максимальным весом?

Как выясняется, существует естественный и обладающий широкими возможностями класс графов, поддерживающих алгоритмы такого типа; фактически такие графы представляют собой «обобщенные деревья», и по причинам, которые вскоре станут ясны, мы будем называть их графами с ограниченной древовидной шириной.

Как и для многих деревьев, многие NP-полные задачи разрешимы для графов с ограниченной древовидной шириной; при этом класс графов с ограниченной древовидной шириной имеет существенное практическое значение, потому что к нему относятся многие реальные сети, в которых возникают NP-полные задачи графов.

Итак, в каком-то смысле этот тип графов служит примером нахождения «правильного» частного случая задачи, который одновременно позволяет построить эффективный алгоритм и включает графы, встречающиеся на практике.

В этом разделе мы определим понятие древовидной ширины, а также предоставим общий подход к решению задач на графах с ограниченной древовидной шириной. В следующем разделе речь пойдет о том, как определить, имеет ли заданный граф ограниченную древовидную ширину.