Computational aspects of treewidth for graph.pdf Древовидная ширина - числовой параметр, характеризующий меру древовидностиграфа. Графы с ограниченной древовидной шириной образуют специальный класс гра-фов, называемых частичными k-деревьями. Этот класс графов был введен четвертьвека назад Н. Робертсоном и П. Д. Сеймуром [1]. Широкий интерес к изучению дре-вовидной ширины графа вызван тем, что многие NP-трудные задачи теории графов,возникающие в различных приложениях, в том числе при моделировании надежностии безопасности компьютерных и коммуникационных систем, полиномиально разреши-мы, если модельный граф - частичное k-дерево. В этих условиях процесс решениязадачи может быть организован по принципу «разделяй и властвуй», причем алгорит-мическая эффективность достигается за счет разложения модельного графа на частис помощью небольших (мощности не более k) сепараторов [2].Древовидная ширина графа вычисляется через специальную графовую структуру,которая называется деревом декомпозиции. Дерево декомпозиции графа G = (V, E)представляет собой пару (X, T), где X = {Xi : i Е I} - семейство подмножеств множе-ства V, называемых «мешками», а T =(I,W) -дерево, узлам которого сопоставленыэти «мешки», и выполняются следующие условия:1) U Xi = V;i e i2) для всякого ребра графа G обязательно имеется хотя бы один «мешок», содер-жащий обе вершины этого ребра;3) для любой вершины v Е V графа G множество узлов {i Е I : v Е X i } индуцируетсвязный подграф, являющийся поддеревом дерева T.Ширина дерева декомпозиции (X,T) равна max{|Xi| - 1}. Древовидная ширинаiei(treewidth) графа G определяется как наименьшая ширина всех допустимых его де-ревьев декомпозиции и обозначается через tw(G). Дерево декомпозиции (X,T) шири-ны tw(G) называется оптимальным деревом декомпозиции графа G. Заметим, что длякаждого связного графа G множество возможных деревьев декомпозиции не пусто иконечно. Когда граф G несвязен, то полагают tw(G) = 0. Следовательно, древовиднаяширина tw(G) может быть вычислена для любого конечного графа G.При условии связности графа G = (V, E) верны естественные границы значенийдревовидной ширины: 1 ^ tw(G) ^ |V| - 1. Древовидная ширина отражает, насколькоблизок граф G к дереву, и определяет размеры его клик и сепараторов: чем меньшеtw(G), тем ближе граф G к дереву и тем меньше у него по мощности клики и сепара-торы. Так, все n-вершинные деревья (n ^ 2) имеют единичную древовидную ширину,размер всякой клики такого дерева равен 2, а каждый сепаратор - точка сочленения.Считается, что граф G обладает ограниченной древовидной шириной, если tw(G) ^ kи k - положительная целая константа, не зависящая от | V|. Например, если G - после-довательно-параллельный граф, то tw(G) ^ 2, а для всякого графа Халина неизменноtw(G) ^ 3. Однако значения tw(G) всегда зависят от |V| для полных графов и графовтипа «сетка» - графов, составленных из правильных многогранников.Установить, имеет ли заданный граф ограниченную древовидную ширину, не все-гда просто. В [3] доказана NP-полнота следующей задачи: для графа G = (V, E)и целого числа 0 < k < |V| верно ли, что tw(G) ^ k? Данное теоретическое пре-пятствие не мешает на практике вычислять древовидную ширину графа во многихситуациях. Во-первых, известны точные неполиномиальные по времени алгоритмынахождения tw(G), основанные на методе динамического программирования и методеветвей и границ [4, 5]. Разработаны также FPT-алгоритмы (Fixed-Parameter Tractablealgorithms) [1, 6], способные при фиксированном k за время O(2k|V|O(1)) дать ответ навопрос: tw(G) ^ k? Во-вторых, найдены алгоритмы полиномиальной сложности длянекоторых специальных классов графов (хордальных, последовательно-параллельныхи др.) [7, 8]. В-третьих, выявлены необходимые полиномиально проверяемые признакичастичного k-дерева [3]. Так, если G = (V, E) -частичное k-дерево, то|E| ^ k|V| - k(k + 1)/2.В-четвертых, к настоящему времени предложены различные схемы приближений [9] иэвристические алгоритмы [10], позволяющие за полиномиальное время находить значе-ния, близкие к истинному значению древовидной ширины графа. И наконец, актуаль-ны границы возможных значений древовидной ширины графа и методы их уточнения.В работе дан краткий обзор современных результатов по проблеме вычисления дре-вовидной ширины. Представлены некоторые нижние и верхние оценки древовиднойширины, связывающие данный параметр с другими числовыми параметрами графа(наименьшей степенью вершины, числом вершинной связности, плотностью, хрома-тическим числом). Проанализировано их качество и сложность вычисления. Пред-ложены и теоретически обоснованы полиномиальные по сложности алгоритмическиеметоды улучшения этих оценок, основанные на немонотонности числовых параметровграфа относительно операции удаления вершин графа и разложении графа сепарато-рами. В частности, доказано, что дерево блоков и точек сочленения графа G определя-ет дерево декомпозиции, ширина которого устанавливает верхнюю границу значенийдля tw(G).Подробное изложение представленных результатов можно найти в [11].

Скачать электронную версию публикации