Software & Systems

Многие проблемы реальной жизни, связанные с дискретными объектами, могут быть смоделированы как оптимизационные задачи на графах. К сожалению, подавляющее большинство оптимизационных задач на графах являются NP-трудными и для них не найдено эффективных (полиномиальных по времени) алгоритмов решения. Возможный путь преодоления этой проблемы - выявление классов графов, для которых NP-трудные задачи эффективно разрешимы. Представительный класс подобных графов образуют частичные k-деревья - графы, обладающие ограниченной древовидной шириной [1]. В него входят, например, ациклические, хордальные, последовательно-параллельные графы, графы Халина.

Другая возможность преодоления высокой вычислительной сложности NP-трудных графовых задач - это организация процедуры поиска оптимального решения по принципу «разделяй и властвуй». Для частичных k-деревьев, когда k - положительная целая константа, этот принцип эффективно реализуется методом динамического программирования на основе дерева декомпозиции графа. Сочетание декомпозиционного метода с декомпозиционным представлением входного графа составляет суть одного из современных подходов разработки эффективных алгоритмов решения большого класса важных практических задач, выражаемых на языке теории графов и комбинаторной оптимизации [1].

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

Дерево декомпозиции и древовидная ширина графа. Везде далее G=(V, E) - неориентированный конечный связный граф без петель и кратных ребер, n=|V| и m=|E|. Пусть G(V¢) - подграф графа G=(V, E), индуцированный множеством V¢ÍV. Говорят, что множество вершин V¢ÍV образует сепаратор графа G=(V, E), если граф G(V \ V¢) имеет более одной компоненты связности. Множество вершин V¢ÍV называется кликой графа G, если G(V¢) – полный граф.

Древовидная ширина графа G=(V, E) определяется через дерево декомпозиции, которое представляет собой пару (M, T), устанавливающую разбиение множества вершин и множества ребер графа G, где M={Xi | i Î I} - семейство подмножеств множества V, называемых мешками, а T=(I, W) - дерево, узлам которого сопоставлены эти мешки. Данное разбиение должно отвечать следующим требованиям [1]:

1) ÈiÎI Xi=V;

2) для всякого ребра графа G обязательно имеется хотя бы один мешок, содержащий обе вершины этого ребра;

3) для любой вершины vÎV графа G множество узлов {iÎI | vÎXi} индуцирует связный подграф, являющийся поддеревом дерева T.

Вершины дерева T принято называть узлами, чтобы избежать путаницы с вершинами графа G. Ширина дерева декомпозиции (M, T) определяется величиной max {(|Xi|-1) | iÎI}. Древовидная ширина (treewidth) графа G, обозначаемая tw(G), есть наименьшая ширина всех допустимых его деревьев декомпозиции. Когда граф G не является связным, считается, что tw(G)=0. Если G - полный n-вершин­ный граф, то tw(G)=n-1. Таким образом, обязательно 0£tw(G)£n–1.

Дерево декомпозиции графа G - это специальная конструкция, которая не только определяет древовидную ширину графа, но и представляет его структуру с точностью до клик и сепараторов: всякая клика графа G всегда целиком вложена в отдельный мешок дерева декомпозиции (M, T); в фундаментальном дереве декомпозиции пересечение любых двух мешков Xi и Xj, отвечающих двум смежным узлам i и j дерева T, неизменно образует сепаратор графа G. Дерево декомпозиции (M, T) без вложенных и кратных мешков имеет O(n) узлов и называется фундаментальным. Оно неизбыточно с точки зрения представления клик и сепараторов графа G. Важно отметить, что всякое дерево декомпозиции (M, T) графа G=(V, E) есть не что иное, как дерево соединений ациклического гиперграфа H=(V, M), ребрами которого выступают мешки Xi, iÎI. Это обстоятельство дает возможность для любой пары (M, T) проверить справедливость указанных свойств 1-3 дерева декомпозиции с помощью полиномиального теста на ацикличность гиперграфа [2, 3].

Древовидная ширина отражает меру древовидности графа G: чем меньше tw(G), тем ближе граф G к дереву и тем меньше у него по мощности клики и сепараторы. Так, все обычные n-вершинные деревья (n³2) имеют единичную древовидную ширину, размер всякой клики такого дерева равен 2, а размер каждого сепаратора равен 1. Граф G обладает ограниченной древовидной шириной, если tw(G)£k и k - положительная целая константа, не зависящая от n. Например, если G - последовательно-параллельный граф, то tw(G)£2, а для всякого графа Халина постоянно tw(G)=3. Ограниченная древовидная ширина - это наследственное свойство графа: если tw(G)£k, то tw(G¢)£k для любого подграфа G¢=G(A), AÍV. Примечательно, что многим приложениям теории графов свойственны графы небольшой древовидной ширины. Например, графы зависимостей между синтаксическими конструкциями естественного языка и графы программ, написанных на языках C++ и Паскаль, имеют древовидную ширину не более 6, а для графов большинства химических соединений характерна ширина не более 4 [1].

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

Рассмотрим задачу П, которую требуется решить для графа G=(V, E) с tw(G)£k, где k - положительная целая константа. Пусть для G известно корневое дерево декомпозиции (M, T), M={Xi | iÎI} и T=(I, W), ширины k и с узлом r в роли корня. Семейство подзадач в данном случае можно задать следующим образом. Определим для всякого узла iÎI множество вершин

Yi={vÎXj | j=i или j - потомок для i в T}.     (1)

Множество Yi индуцирует в G подграф Gi=G(Yi), а в T - поддерево с корневым узлом i. Примечательно, что Yr=V и Gr=G. Тогда в качестве отдельной подзадачи Пi можно рассматривать решение задачи П для Gi, iÎI.

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

1)     для заданного графа G=(V, E) строится дерево декомпозиции ширины k, которое затем преобразуется в корневое дерево декомпозиции (M, T) той же ширины;

2)     решается задача П с помощью корневого дерева декомпозиции (M, T).

В данной статье рассматривается только второй этап. Подходы к реализации первого этапа можно найти, например, в работах [1, 3, 4]. Второй этап, в свою очередь, состоит из двух фаз:

-      обход всех узлов дерева T снизу вверх от листьев к корню r - вычисление необходимой информации и нахождение значений характеристик подзадач;

-      обход всех узлов дерева T сверху вниз от корня r к листьям для конструирования оптимального решения задачи П для исходного графа G.

Вся нужная информация вычисляется и хранится в виде таблиц. Каждому узлу iÎI дерева T соответствует таблица Ai, которая содержит информацию по задаче Пi. Метод динамического программирования требует, чтобы эти таблицы обладали следующими свойствами:

-      для каждого узла iÎI решение задачи Пi находится исключительно из таблицы Ai;

-      для каждого листа iÎI дерева T таблица Ai вычисляется непосредственно из G(Xi);

-      для каждого внутреннего узла iÎI таблица Ai создается из G(Xi) и таблиц, которые отвечают прямым потомкам узла i в T.

Использование дерева декомпозиции способствует выполнению указанных выше свойств таблиц, поскольку для каждого узла iÎI дерева T справедливо высказывание: вершины графа Gi, смежные с вершинами, находящимися вне Gi, обязательно содержатся в мешке Xi. Иными словами, графы Gi=G(Yi) и G(V \ Yi) связаны между собой в G только с помощью вершин из Xi. Заметим, что таких вершин не более k+1. Следовательно, когда необходимо от таблиц, созданных для потомков внутреннего узла i, перейти к таблице Ai, то достаточно исследовать только вершины из Xi (вместо Yi) и применять лишь таблицы прямых потомков узла i.

Обход дерева T с O(n) узлами осуществим за время O(n), где n=|V|. Поэтому для получения эффективного алгоритма реализации двух фаз динамического программирования по дереву декомпозиции необходимо, чтобы каждая таблица Ai вычислялась и обрабатывалась эффективно относительно n. Найти точное решение задачи Пi для каждого узла i дерева T можно всегда полным перебором на основе таблицы Ai, в которой перечислены различные подмножества (как претенденты на оптимальное решение) множества Xi, и таблиц прямых потомков, если такие существуют. Предположим, что всякая вершина из Xi может находиться по отношению к возможному решению в q состояниях. Например, в задаче о вершинном покрытии q=2 («принадлежит вершинному покрытию», «не принадлежит вершинному покрытию»), а в задаче о доминирующем множестве q=3 («входит в доминирующее множество», «доминирует, но не входит в доминирующее множество», «не доминирует»). Тогда для узла i, являющегося листом в T, таблица Ai имеет размер O(k · qk), так как |Xi|£k+1, iÎI. Размер таблицы Ai для внутреннего узла i с двумя прямыми потомками может достигать O(k · q2k). Ясно, что, чем больше арность дерева T (число прямых потомков узлов этого дерева), тем большего размера таблицы могут возникать в процессе вычислений. По этой причине традиционно оперируют корневым бинарным деревом декомпозиции.

Если обработка одной строки каждой таблицы Ai, iÎI, требует nO(1) времени, то время работы алгоритма, основанного на динамическом программировании по дереву декомпозиции, составляет f(k) · nO(1). Здесь f(k) - функция, не зависящая от n и содержащая экспоненциальные составляющие вида O(qk), O(q2k), O(q3k) и т.п. Такие алгоритмы называют FPT (Fixed-Parameter Tractable)-алго­ритмами [5]. Они экспоненциальные лишь по отношению к параметру k и полиномиальные относительно n. При фиксированном значении параметра FPT-алгоритмы теоретически эффективны по времени выполнения. Однако практически эффективными они являются только при малых значениях параметра. Это является главным препятствием практического применения FPT-ал­горитмов, основанных на динамическом программировании по дереву декомпозиции. Поэтому актуальны различные алгоритмические приемы, направленные на предобработку входных данных с целью снижения числа и размера таблиц динамического программирования. Таким приемом, например, является приспособление дерева декомпозиции исходного графа к решаемой графовой задаче: снижение арности дерева до двух, определение различных типов узлов и т.п.

Важно отметить, что подобные приемы не дают дополнительных алгоритмических возможностей. Между тем их использование в ряде случаев позволяет снизить потребности FPT-алгоритмов в вычислительных ресурсах. Предлагается FPT-ал­горитм решения задачи о вершинном покрытии с шириной дерева декомпозиции графа в роли параметра. В данном алгоритме применяется специальное преобразование заданного дерева декомпозиции (введение дополнительных узлов-сепара­торов) и привлекается аппарат реляционной алгебры (алгебры таблиц) [2].

Вычисление наименьшего вершинного покрытия. Подмножество V¢ÍV образует вершинное покрытие графа G=(V, E), если каждое ребро из E инцидентно хотя бы одной вершине из V¢. Покрытие V¢ называется наименьшим, если число вершин в нем наименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытии графа G называется числом покрытия этого графа и далее обозначается через b(G). В оптимизационной постановке задача о вершинном покрытии графа формулируется следующим образом. Задан граф G=(V, E). Требуется найти наименьшее вершинное покрытие графа G. Эта задача является типичной NP-трудной задачей на графах, к которой сводятся многие подобные задачи. Применительно к графам ограниченной древовидной ширины будем полагать, что исходный граф G=(V, E) задан вместе со своим деревом декомпозиции ширины k, где k - положительная целая константа.

Прежде чем приступить к решению задачи методом динамического программирования, предлагаем преобразовать заданное дерево декомпозиции графа G следующим образом.

Шаг 1. Удалить из дерева декомпозиции кратные и вложенные мешки, то есть получить фундаментально дерево декомпозиции графа G.

Шаг 2. Выбрать произвольный узел rÎI в роли корня и снизить арность дерева до двух. Последнее действие осуществить так. Если внутренний узел iÎI обладает одним или двумя прямыми потомками, то ничего не делать. Если внутренний узел iÎI имеет в качестве прямых потомков узлы j1, …, jd, d³3, то выполнить клонирование узла i в узлы i1, …, id-1 и приписать каждому из них мешок Xi. Отношение подчиненности между узлами установить, как показано на рисунке 1.

Шаг 3. Для любых двух узлов i, jÎI, смежных в T и имеющих мешки Xi и Xj соответственно, добавить промежуточный узел s и сопоставить ему множество вершин S=XiÇXj¹Æ (рис. 2). Заметим, что S - сепаратор графа G.

Таким образом, исходное дерево декомпозиции пополнится O(n) узлами. Результирующее дерево декомпозиции (M, T), M={Xi | iÎI}, T=(I, W), будет иметь O(n) узлов, ширину k и узел r в роли корня. В нем возможны только четыре типа узлов:

-      узел-лист - узел, у которого нет потомков;

-      узел-сепаратор - узел s с одним прямым потомком j; если i - родитель узла s, то Xs=XiÇ ÇXj¹Æ, XsÍXi, XsÍXj;

-      узел-расширение - узел i с одним прямым потомком s; в данном случае XsÍXi;

-      узел-объединение - узел i с двумя прямыми потомками l и j (здесь XlÈXjÍXi).

В качестве подзадачи рассмотрим решение задачи о вершинном покрытии для графа Gi=G(Yi), где Yi - множество вершин, определенное по (1) и отвечающее поддереву дерева T с корнем iÎI. Пусть c(Z) - число вершин, образующих некоторое вершинное покрытие Z графа Gi. Данная величина является естественной характеристикой покрытия и целевой функцией в задаче о вершинном покрытии.

При обходе дерева T снизу вверх и вычислении таблиц Ai следует различать четыре возможные ситуации, соответствующие четырем типам узлов. Дадим описание этих ситуаций, используя язык реляционной алгебры.

Ситуация 1: узел-лист i с мешком Xi. Задача для графа G(Xi) решается полным перебором. Для этого создается таблица Ai по следующим правилам. В таблице p+1 столбцов и 2p строк, где p=|Xi|, отдельная строка для каждого из 2p различных подмножеств ZÍXi. Состав вершин, входящих в Z, представляется битовой шкалой b: b(v) = 1, если vÎZ, и b(v)=0 в противном случае. Последний столбец c(Z) содержит характеристику Z: c(Z)=|Z|, если Z - вершинное покрытие для графа G(Xi), иначе c(Z)=¥. Заметим, что |Z|=S b(v), vÎXi.

Ситуация 2: узел-сепаратор s с одним прямым потомком j. В данном случае XsÍXj. Пусть для узла j ранее уже была построена таблица Aj. Тогда таблица As вычисляется по формуле

As=pS(Aj),                                                          (2)

где p - реляционная операция проекции, которая выбирает из таблицы Aj подмножество столбцов S=XsÈ{c(Z)}. В полученной таблице As возможны строки, совпадающие по индикаторам вершин из Xs и имеющие разные значения целевой функции c1(Z), c2(Z), …, ch(Z), h³1. Поэтому для всех таких строк полагается

c(Z)=min {c1(Z), c2(Z), …, ch(Z)}                         (3)

и в As оставляется только одна из них. После этого результирующая таблица As содержит только ту информацию из Aj, которая необходима для согласования ее с таблицей Ai, где i - родитель узла s.

Ситуация 3: узел-расширение i с одним прямым потомком s, для которого XsÍXi. Пусть для узла s ранее уже была создана таблица As. Вначале формируется таблица Ai так, как будто бы узел i является листом. Затем таблица Ai связывается с таблицей As с помощью реляционной операции естественного соединения (´), и результат записывается в Ai:

Ai=Ai´As.                                                                 (4)

Поскольку XsÍXi, при выполнении естественного соединения в таблице Ai появляется лишь один дополнительный столбец со значениями c(Z) из таблицы As. Пусть Ai.c(Z) и As.c(Z) - значения характеристики для ZÍXi, включенные в результирующую таблицу Ai из исходных таблиц Ai и As соответственно. В этих обозначениях формула пересчета значений c(Z) для Ai имеет вид

c(Z)=Ai.c(Z)+As.c(Z)-S b(v),                                (5)

где суммирование берется по всем vÎXs.

Ситуация 4: узел-объединение i с двумя прямыми потомками l и j. Заметим, что в данном случае узлы l и j являются узлами-сепараторами и XlÈXjÍXi. Пусть им соответствуют таблицы Al и Aj. Аналогично ситуации 3 вначале формируется таблица Ai так, как будто бы узел i является листом. Далее по формулам (4), (5) таблица Ai связывается с таблицей Al, а затем полученная таблица - с таблицей Aj. Таким образом, ситуация 4 сводится к двукратному повторению действий, определенных для ситуации 3.

Как только достигается корневой узел r и вычисляется таблица Ar, значение числа вершинного покрытия графа G находится по формуле

b(G)=min{c(Z) | ZÍXr}.                                 (6)

Для построения самого вершинного покрытия следует выполнить спуск по T от корня к листьям.

Во всех четырех ситуациях размер формируемых таблиц составляет O(k ·2k), где k - ширина заданного дерева декомпозиции исходного гра- фа G. Эта оценка достигается за счет введения в дерево декомпозиции узлов-сепараторов:

-      для всякого узла-листа i таблица Ai имеет размер O(k·2k), поскольку |Xi|£k+1, iÎI;

-      операция проекции, используемая в ситуации 2, не увеличивает размер таблицы;

-      операция естественного соединения, применяемая в ситуации 3 для узла-расширения i с прямым потомком s, дает таблицу размера O(k·2k), поскольку XsÍXi. Между тем в общем случае (для любого отношения вложенности между Xs и Xi) операция естественного соединения двух таблиц размера O(k·2k) приводит к таблице размера O(k·22k).

Как уже указывалось, обход дерева T всегда можно реализовать за время O(n). Выполнение проверки, является ли подмножество ZÍXi вершинным покрытием для графа G(Xi), также осуществимо за время O(n). Таким образом, время работы алгоритма и потребность его в памяти сопоставимы с O(k·2k·n). Значит, чем меньше древовидная ширина графа G, тем меньше вычислительных ресурсов требуется для нахождения вершинного покрытия этого графа.

Заметим, что в ситуации 4 не важно, сколько прямых потомков имеет узел-объеди­не­ние. Если их d³2, то действия, определенные для ситуации 3, надо повторить d раз. Очевидно, что исключение шага 2 по преобразованию исходного дерева декомпозиции (снижение арности дерева) может существенно сократить число узлов в T и уменьшить практические потребности алгоритма в вычислительных ресурсах. При этом возможно усложнение программной реализации алгоритма применительно к ситуации 4.

Иллюстрация работы алгоритма. Пусть задан граф G вместе с деревом декомпозиции ширины 2 (рис. 3). Дерево декомпозиции графа G, полученное после преобразований (в данном случае только добавления узлов-сепараторов 2, 5, 6 и выделения узла 7 в роли корня), изображено на рисунке 4. Найдем наименьшее вершинное покрытие графа G с помощью предложенного выше алгоритма.

Начнем с узла 1. Это узел-лист. Узел 2 является узлом-сепаратором и родителем для узла 1. Таблицы A1 и A2 отвечают данным узлам (рис. 5а и 5б). Согласно формулам (2), (3), A2=pg(A1). Аналогично узлам 4 и 5 соответствуют таблицы A4, A5 (рис. 5в и 5г) и A5=p y (A4). Узел 3 - это узел-объедине­ние по отношению к узлам 2 и 5. Для него таблица A¢3 (рис. 5д) содержит локальную информацию для подграфа G(X3). Естественное соединение A¢3 с таблицей A2, а затем с таблицей A5 по формулам (4) и (5) дает таблицу A3 (рис. 5е). Узел 6 – вновь узел-сепаратор, для которого A6=p yw (A3) (рис. 5ж). Корневой узел 7 - это узел-расширение по отношению к узлу 6. В соответствии с формулами (4) и (5) таблица A7 имеет вид, представленный на рисунке 5з. Таблица A7 отвечает корневому узлу. Применение формулы (6) к A7 дает b(G)=3.

Спуск по дереву декомпозиции от корня к листьям определяет следующие наименьшие вершинные покрытия графа G: {x, y, g}, {x, g, u}, {y, w, g}, {y, w, v}. Заметим, что для исходного графа допустимы деревья декомпозиции, отличные от дерева, указанного на рисунке 3. Решение задачи о вершинном покрытии на их основе приведет, возможно, к другим оптимальным решениям, хотя неизменным будет значение b(G)=3.

Предложенный алгоритм можно применять для взвешенной версии задачи о вершинном покрытии, а его идеи - для решения других подобных задач: нахождения наибольшего независимого множества вершин, поиска наибольшей клики, отыскания наименьшего доминирующего множества графа. Использование языка реляционной алгебры в описании алгоритма неслучайно. Как видно из изложенного в работе процесса согласования таблиц динамического программирования в задаче о вершинном покрытии, этот процесс подобен процессу реализации запроса к реляционной БД, где в качестве исходных отношений выступают таблицы, отвечающие узлам дерева декомпозиции, как будто бы все они есть листья. Каждому такому запросу свойственны свои формулы пересчета характеристик решений. Реляционный взгляд на процесс динамического программирования по дереву декомпозиции позволяет при разработке алгоритмов использовать такие свойства ациклических БД, как квазистягиваемость и существование монотонных планов соединения отношений.

Литература

1. Bodlaender H.L. Discovering treewidth. In Proceedings of the 31st Conference SOFSEM 2005, Springer-Verlag, Lecture Notes in Computer Science 3381, 2005, pp. 1-16.

2. Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.

3. Быкова В.В. Алгоритм построения дерева декомпозиции гиперграфа на основе ацикличности // Программные продукты и системы. 2011. № 1(93). С. 64-69.

4. Быкова В.В. Рекуррентные методы вычисления древовидной ширины гиперграфа // Изв. Томского политех. ун-та. 2011. Т. 318. № 5. С. 5-10.

5. Быкова В.В. FPT-алгоритмы и их классификация на основе эластичности // Прикл. дискр. математика. 2011. № 2(12). С. 40-48.