FPT-алгоритмы на графах ограниченной древовидной ширины | ПДМ. 2012. № 2(16).

FPT-алгоритмы на графах ограниченной древовидной ширины

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

FPT-algorithms on graphs of limited treewidth.pdf ВведениеПараметризированный подход к оценке сложности вычислений - естественныйспособ справиться с трудноразрешимостью задач, которые охарактеризованы какNP-трудные в соответствии с классической дихотомией P против NP [1]. Основнаяидея параметризированного подхода состоит в том, чтобы с помощью некоторого чис-лового параметра учесть структуру исходных данных и выделить основной источ-ник трудноразрешимости задачи. Параметризированный подход позволяет исследо-вать различные параметризации одной и той же задачи, каждая из которых можетприводить или не приводить к FPT-алгоритмам. Такие алгоритмы представляют ин-терес для алгоритмической практики, так как при ограниченном значении параметравремя их выполнения полиномиально зависит от длины входа алгоритма [2].В настоящее время уже известны некоторые специальные методы проектированияFPT-алгоритмов. Наиболее известный из них - метод динамического программиро-вания на основе дерева декомпозиции, автором которого считается Г. Бодлаендер [3].Этот метод ориентирован на класс задач, решение которых ищется в конечной области.При этом поиск решения подразумевает нахождение одного из допустимых решений(в задачах разрешения и удовлетворения ограничений) или оптимального решения(в задачах комбинаторной оптимизации). Такие задачи в литературе часто называ-ют задачами выбора [4]. Параметризация задачи в данном случае осуществляется подревовидной ширине входного графа. Несмотря на теоретическую привлекательностьметода динамического программирования по дереву декомпозиции, практическое егоприменение ограничивается двумя проблемами, первая из них связана с высокимипотребностями в памяти получаемых FPT-алгоритмов, а вторая - с вычислением дре-вовидной ширины и построением дерева декомпозиции. В данной работе предложенысредства решения первой из указанных проблем. Методы решения второй проблемырассмотрены в работе автора [5].1. Дерево декомпозиции и древовидная ширина графаДинамическое программирование по дереву декомпозиции - это сочетание деком-позиционного подхода к решению задачи выбора с декомпозиционным представлениемвходного графа, когда выделение подзадач и построение их решений осуществляетсяисходя из этого представления. Дерево декомпозиции графа - э т о специальная кон-струкция, которая описывает структуру графа «с точностью до клик и сепараторов» иопределяется следующим образом. Пусть задан связный граф G = (V, E ) , n = | V| ^ 1и m = |E| ^ 1. Дерево декомпозиции графа G - пара (M, T ) , задающая разбиениемножества вершин и множества рёбер этого графа, где M = { X j : i Е I} - семействоподмножеств множества V, называемых «мешками», а T = (I, W) -дерево, узламкоторого сопоставлены эти «мешки». Вершины дерева T принято называть узлами,чтобы избежать путаницы с вершинами графа G. Семейство M = { X j : i Е I} имножество W рёбер дерева T = (I, W) такие, что справедливы следующие условия [3]:1) объединение всех подмножеств, образующих «мешки», даёт множество V;2) для всякого ребра графа G существует хотя бы один «мешок», содержащий обевершины этого ребра;3) для любой вершины v графа G множество узлов {i Е I : v Е X j } , «мешки» ко-торых содержат эту вершину, индуцирует связный подграф, являющийся под-деревом дерева T.Ширина дерева декомпозиции ( M , T ) равна max{|Xj| - 1}. Древовидная ширинаi e i(treewidth) графа G определяется как наименьшая ширина всех допустимых его дере-вьев декомпозиции и обозначается через tw(G). Дерево декомпозиции ширины tw(G)называется оптимальным, а без кратных и вложенных «мешков» - фундаментальным.В фундаментальном дереве декомпозиции всегда O(n) узлов и к нему можно перейтиза время O(111). Для tw(G) верны естественные границы: 1 ^ tw(G) ^ n - 1. Считается,что граф G обладает ограниченной древовидной шириной, если tw(G) ^ k и k естьцелая положительная константа, не зависящая от n.Заметим, что всякое дерево декомпозиции (M, T) графа G = (V, E) есть не чтоиное, как дерево соединений ациклического гиперграфа H = (V, M ) , рёбрами котороговыступают «мешки» этого дерева [6]. При этом граф смежности вершин гиперграфа Hявляется некоторой (не обязательно минимальной)триангуляцией графа G.2. Описание методаПусть задана некоторая параметризированная задача П, которую надо решить дляграфа G = (V, E). Полагаем, что в качестве параметра задачи взята древовидная ши-рина tw(G) и tw(G) ^ k, k - целая положительная константа. Кроме того, считаем,что задача П сформулирована в оптимизационной конструктивной постановке, то естьзадана некоторая числовая характеристика (целевая функция) графа G = (V, E ) , ко-торую надо оптимизировать и указать решение, отвечающее оптимальному значениюэтой характеристики.Пусть для исходного графа G = (V, E) известно корневое дерево декомпозиции(M, T ) , M = { X j : i Е I } , T = (I, W ) , ширины k и с узлом r в роли корня. Семействоподзадач в данном случае можно задать следующим образом. Определим для всякогоузла i Е I множество вершин:Y = {v Е Xj : j = i или j -потомок для i в T } . (1)Множество Y индуцирует в G подграф Gi = G(Yj), а в T - поддерево с корневымузлом i. Примечательно, что У = V и Gr = G. Тогда в качестве подзадачи ni можнорассматривать решение задачи П применительно к Gi , i Е I. Понятно, что для каж-дой конкретной задачи П специфичны характеристика решения и рекуррентные про-цедуры, связывающие решения подзадач. Между тем сценарий действия алгоритмов,основанных на динамическом программировании по дереву декомпозиции, общий.Работа подобных алгоритмов включает в себя два этапа. На первом этапе для ис-ходного графа G = (V, E) строится корневое дерево декомпозиции (M, T) ширины k.На втором этапе решается задача П с помощью (M, T): сначала обход всех узлов дере-ва T снизу вверх (от листьев к корню r) с целью вычисления необходимой информа-ции и нахождения значений характеристик подзадач; затем обход всех узлов дерева Tсверху вниз (от корня r к листьям) с целью конструирования оптимального решениязадачи П для исходного графа G. При этом вся нужная информация вычисляетсяи хранится в виде таблиц. Каждому узлу i Е I дерева T соответствует таблица Ai,которая содержит информацию по задаче ni.Процесс формирования таблиц и решений отвечает следующим необходимым тре-бованиям. При любом i Е I решение задачи ni находится исключительно из таб-лицы Ai. Для всякого листа i Е I дерева T соответствующая таблица вычисляетсянепосредственно из G(Xi ) . Для каждого внутреннего узла i Е I таблица создается изинформации о G ( X i ) и таблиц, которые отвечают прямым потомкам узла i в T. Дереводекомпозиции гарантирует выполнение указанных требований, поскольку справедливоУ т в е р ж д е н и е 1 [3]. Пусть i Е I - произвольный внутренний узел дерева T. Вер-шины графа Gi = G(Yj), которые смежны с вершинами, находящимися вне Gi , обя-зательно содержатся в «мешке» Xi (и таких вершин не более k + 1). Иными словами,графы G(Yj) и G(V\Yj) «связаны» между собой в G только с помощью вершин из X i .В общем случае поиск точного решения задачи ni для каждого узла i дерева Tосуществляется полным перебором в Ai , где представляются различные подмноже-ства множества вершин как претенденты на оптимальное или допустимое решение.Очевидно, что время подъёма и спуска по дереву декомпозиции зависит отчисла иразмера создаваемых таблиц динамического программирования, а также от времениобработки каждой строки такой таблицы.3. Достаточные условия FPT-разрешимости относительнодревовидной шириныОказывается, что описанный выше метод динамического программирования на ос-нове дерева декомпозиции приводит к FPT-алгоритму относительно древовидной ши-рины, если задача выбора может быть сформулирована в монадической логике второ-го порядка. Монадическая логика второго порядка (Monadic Second Order Logic, илиMSOL) для графа G = (V, E) -язык исчисления предикатов выражения его свойств.Предикатные формулы в MSOL, описывающие свойства графа G, состоят из следую-щих символов [7]:- предметных переменных vi и ej, при этом каждой переменной vi соответствуетотдельная вершина, а переменной ej - отдельное ребро графа G (1 ^ i ^ n = |V|,1 ^ j ^ m = |E|);- предметных переменных V и Ej, где переменной Vj отвечает некоторое подмноже-ство множества вершин V, а переменной Ej -некоторое подмножество множестварёбер графа G (0 ^ i ^ 2n, 0 ^ j ^ 2m);- предикатных переменных и логических связок &, V, -,- кванторов V и 3, запятых и круглых скобок.В состав атомарных формул входят:- предикат совпадения (ж = ж'). Принимает значение «истина», если вершины (рёб-ра) ж и ж' графа G совпадают;- предикат принадлежности (ж Е X ) , где предметная переменная ж отвечает вершине(ребру) графа G, а переменная X - подмножеству вершин (рёбер) этого графа;- предикат инцидентности Incident(vj,ej). Принимает значение «истина», если вер-шина Vj и ребро ej инцидентны в G.Все другие формулы MSOL формируются из атомарных формул MSOL с помощьюлогических связок, кванторов 3ж и Vx (ж - предметная переменная, соответствующаявершине или ребру графа G) и кванторов 3X и VX (X - предметная переменная,отвечающая подмножеству вершин или ребер графа G). Заметим, что монадическаялогика первого порядка (Monadic First Order Logic, или MFOL) отличается от MSOLлишь тем, что в ней не допускаются кванторы 3X и VX.Всякое свойство графа G может быть задано некоторым предикатом P. Предикат Pдля графа G (обозначается через P(G)) принимает значение «истина», если рассмат-риваемое свойство выполняется для этого графа, и «ложь» в противном случае. Неко-торые популярные свойства графа, выраженные в виде формул MSOL, представленыв таблице. Из всех указанных в этой таблице свойств только свойства связности игамильтоновости графа не могут быть выражены в MFOL. Заметим, что длина всехформул, приведённых в таблице, не зависит от размера (числа вершин и рёбер) гра-фа G. Такие формулы MSOL называются конечными.Пусть граф G имеет ограниченную древовидную ширину, то есть tw(G) ^ k, гдеk - некоторая целая положительная константа. Пусть проверяемое свойство графа Gпредставлено в виде MSOL-формулы P и |P| -длина этой формулы.Т е о р е м а 1 (теорема Курселя [7]). Для графа G = (V, E) с tw(G) ^ k существуетфункция f : N х N ^ N и алгоритм, который проверяет истинность P(G) за времяO(n f (|P|,k)).Очевидно, что если величина | P| не зависит от n = | V| и m = |E|, например, явля-ется постоянной или зависит только от k, то по теореме Курселя для графа, удовлетво-ряющего условиям теоремы 1, существует алгоритм со временем работы O(n f (k)), тоесть FPT-алгоритмотносительно древовидной ширины графа G. Таким образом, вся-кое свойство графа G = (V, E ) , выраженное в виде конечной формулы MSOL, можетбыть проверено за полиномиальное время при условии, что граф G имеет ограни-ченную древовидную ширину. Теорема Курселя демонстрирует широту класса FPT-разрешимых графовых задач, но не даёт точного ответа, как устроен FPT-алгоритмдля задачи, отвечающей условиям этой теоремы. Единственное, что известно, - этообщая схема такого алгоритма, описанная выше в п. 2.Для применения теоремы Курселя на практике необходимо: найти MSOL-формулупроверяемого свойства графа; убедиться, что заданный граф G имеет древовиднуюширину tw(G) ^ k; построить для G дерево декомпозиции ширины k. Относительнопоследних действий известен следующий результат.Формулы MSOL, определяющие некоторые свойства графаСвойство графа Предикат Формула MSOL, определяющаяпредикатСовпадение рёбер eJ и eJ e i EJ (Vvi)(Incident(vi, eJ)) ^ (Incident(vi, eJ))Смежность вершин vj и Vj Adjacent (vJ, VJ) -(vJ = vJ)&(3ei ) (Incident(vj,ei) && Incident(vJ, ei))Vi - независимое множе-ство вершин IndependentSet(Vi) (Vv2)(Vv3)((v2 Е Vi & v3 Е Vi) ^-Adjacent (v2, v3))Vi - вершинное покрытие VertexCover(Vi) (Ve2)(3v3)(v3 Е Vi & Incident(v3,e2))Vi - клика Clique(Vi) (Vv2)(Vv3)((v2 Е Vi & v3 Е Vi) ^Adjacent(v2, v3))Vi - доминирующее мно-жество DominatingSet(Vi) (Vv2)(v2 Е Vi V (3v3)(v3 Е Vi && Adjacent(v2, v3)))Вершинная k-раскраска VertexColorable(Vi,..., Vfc)(Vvo)(vo Е Vi V ... V vo Е Vfc )&IndependentSet(Vi) & ...& IndependentSet(Vk)Ei - связность Connected(Ei)(VV2)(VV3)( -(3v4)(v4 Е V2))V(-(3vs)(v5 Е V3))V(3ve)(-(ve Е V2) & - (ve Е V3))V(3er)(3v8)(3vg)(e7 Е Ei & vg Е V2 &v9 Е V3 & Incident(v8, e7) &Incident (vg, e7))Ei - гамильтонов цикл HamCycle(Ei)Connected(Ei) & (Vv2)(3e3)(3e4)(e3 Е Ei & e4 Е Ei & -(e3 = e4) &Incident (v2, e3) & Incident (v2, e4) &(Ve5)((e5 Е Ei & Incident(v2, e5)) ^(e5 = e3 V e5 = e4)))Т е о р е м а 2 (Г. Бодлаендер, Т. Клокс [8]). Существует функция f : N х N ^ N иалгоритм, который за время O(n f (k)) проверяет, имеет ли граф G древовидную ши-рину tw(G) ^ k, и если да, то строит для G дерево декомпозиции ширины k.Данная теорема свидетельствует о том, что условия применимости теоремы Курсе-ля, касающиеся древовидной ширины графа, могут быть проверены соответствующимFPT-алгоритмом за полиномиальное время.4. Вычислительная сложность метода и её преодоление с помощьюBfcS-дереваДинамическое программирование - метод, рекурсивный по своей природе. Однакорекурсивная реализация данного метода при числе подзадач больше единицы неми-нуемо влечёт неполиномиальное время вычислений относительно длины входных дан-ных [9]. Согласно соотношению (1), число подзадач на каждом шаге динамическогопрограммирования по дереву декомпозиции определяется арностью данного дерева.Очевидно, что в общем случае эта арность больше единицы. Поэтому для полученияFPT-алгоритма необходимо динамическое программирование осуществлять итераци-онно с помощью табличной техники. Между тем эта техника порождает проблемупамяти для размещения создаваемых таблиц, поскольку размер всякой таблицы экс-поненциально зависит от арности и древовидной ширины применяемого дерева деком-позиции.Пусть для задачи П, решаемой на графе G = (V, E) с tw(G) ^ k, построено корне-вое дерево декомпозиции (M, T ) , M = { X i : i Е I } , T = (I, W ) , ширины k и с узлом rв роли корня. Если дерево T содержит |I| = O(n) узлов, то придинамическом програм-мировании придется хранить O(n) таблиц Ai , i Е I. Предположим, что всякая вершинаиз Xj может находиться по отношению к возможному решению в q состояниях. Напри-мер, в задаче о вершинном покрытии q = 2 («принадлежит вершинному покрытию»,«не принадлежит вершинному покрытию»), а в задаче о доминирующем множествеq = 3 («входит в доминирующее множество», «не входит в доминирующее множество,но доминируется», «не входит в доминирующее множество и не доминируется»). Тогдатаблица Aj узла i, являющегося листом в T, имеет размер O(kqk), так как |Xj| ^ k + 1.Размер таблицы Aj для внутреннего узла i с двумя прямыми потомками может до-стигать O(kq3k). Ясно, что чем больше арность дерева T (число прямых потомковдля узлов этого дерева) и чем больше ширина (M, T ) , тем большего размера табли-цы могут возникать в процессе вычислений и тем больше времени потребуется дляих обработки. Таким образом, проблема памяти - серьезное препятствие практиче-ского применения FPT-алгоритмов, основанных на динамическом программированиипо дереву декомпозиции. Эта проблема является предметом теоретических исследо-ваний многих авторов [3, 8, 10, 11]. В работах практической направленности преиму-щественно предлагаются различные улучшения дерева декомпозиции. Наиболее из-вестное в этом отношении - «хорошее» дерево декомпозиции (nice tree decomposition),описанное Т. Клоксом [12]. Его принято называть деревом декомпозиции Kloks-вида(или просто Kloks-деревом).Корневое дерево декомпозиции (M, T ) , M = { X j : i Е I } , T = (I, W ) , отвечаетKloks-виду, если оно удовлетворяет следующим условиям:1) каждый узел дерева имеет не более двух узлов прямых потомков;2) если узлу i непосредственно подчинены два узла l и j, то Xj = Xi = Xj (i -узел-соединение);3) если узел i располагает одним прямым потомком j, то- либо |Xj| = |Xj| + 1 и Xj С Xj (i - узел-вставка),- либо |Xj| = |Xj| - 1 и Xj С Xj (i - узел-удаление).В работе [12] доказано, что всякое фундаментальное дерево декомпозиции (M, T ) ,имеющее ширину k и O(n) узлов, может быть преобразовано за время O(k2n) в Kloks-дерево, которое обладает той же шириной и O(kn) узлами. Заметим, что мощности«мешков» Kloks-дерева, соответствующие смежным узлам этого дерева, различаютсяне более чем на единицу. Такая сглаженность и бинарность Kloks-дерева даёт возмож-ность размер создаваемых таблиц удерживать в пределах оценки O(kqk). Понятно, чтоэто достигается за счет увеличения (возможно в k раз) числа узлов дерева и таблицдинамического программирования.Желательно иметь такой вид дерева декомпозиции, который бы обеспечивал ком-промисс между размером и числом таблиц динамического программирования. Для до-стижения этой цели предлагается использовать бинарное сепараторное дерево деком-позиции (или просто BfeS-дерево). Для него характерны следующие особенности: пе-реход от бинарного корневого дерева декомпозиции к BfeS-дереву увеличивает числотаблиц не более чем в два раза; оно, как и Kloks-дерево, позволяет удерживать раз-мер всякой таблицы динамического программирования в пределах оценки O(kqk); длявычисления таблиц динамического программирования по BfeS-дереву возможно при-влечение аппарата реляционной алгебры и свойств ациклических баз данных. Дадимпояснение и обоснование сказанному.Корневое дерево декомпозиции (M, T ) , M = { X j : i Е I } , T = ( I , W ) , графа Gназовём BfeS-деревом, если в нём каждый узел имеет не более двух прямых потомкови относится к одному из четырёх типов узлов:1) узел-лист - узел, у которого нет потомков;2) узел-сепаратор - узел s с одним прямым потомком j и узлом i в роли родителя.Всегда Xs - сепаратор графа G и Xs = Xi П Xj = 0, Xs С Xj, Xs С Xj;3) узел-расширение - узел i с одним прямым потомком s. В данном случаеXs С Xi;4) узел-соединение - узел i с двумя прямыми потомками l и j. Здесь X^ U Xj С Xi .У т в е р ж д е н и е 2. Всякое фундаментальное дерево декомпозиции (M, T) гра-фа G, где M = { X i : i G I } , T = (I, W ) , имеющее ширину k и 1I1 = O(n) узлов,может быть преобразовано за время O(n) в Б&Б-дерево, которое обладает той же ши-риной и O(n) узлами.Доказательство. Преобразование заданного дерева декомпозиции (M, T)в Б&Б-дерево можно выполнить за два шага.Ш а г 1. Сначала выбрать любой узел r G I в роли корня. Затем снизить арностьдерева до двух следующим образом. Если внутренний узел i G I обладает одним илидвумя прямыми потомками, то ничего не делать. Если внутренний узел i G I имеетв качестве прямых потомков узлы ji,... ,jd, d ^ 3, то выполнить «клонирование» узла iв узлы il,... , id-i и приписать каждому из них «мешок» Xi . Отношение подчинённостимежду узлами установить так, как показано на рис. 1. В результате будет добавленоO(n) узлов.Рис. 1. Схема преобразования дерева декомпозиции к бинарному видуШ а г 2. Для любых двух узлов i, j G I, смежных в T и имеющих «мешки» Xiи Xj соответственно, добавить промежуточный узел s и сопоставить ему в качестве«мешка» множество вершин Xs = Xi П Xj = 0 (рис. 2). Исходя из известных свойствдерева декомпозиции [5, с. 67, утверждение 1], множество Xs - сепаратор графа G и,следовательно, s есть узел-сепаратор. Таких узлов будет добавлено O(n).Рис. 2. Схема формирования узла-сепаратораОбщее число узлов в BfeS-дереве составит O(n). Время реализации каждого шага -также O(n). Ни одно из действий, предусмотренных шагами 1 и 2, не увеличиваетвместимость «мешков» для (M, T ) , поэтому значение k не изменится. ПостроенноеBfeS-дерево - дерево декомпозиции графа G, так как оно очевидным образом отвечаетусловиям 1-3 определения дерева декомпозиции. Чтобы убедиться, что BfeS-дерево сохраняет размер всех создаваемых в процессединамического программирования таблиц в пределах оценки O(kqk), сначала рассмот-рим, как это достигается при применении Kloks-дерева. Здесь целесообразно прибег-нуть к языку реляционной алгебры (алгебры таблиц) [6].Пусть (M, T ) , M = { X i : i Е I } , T = (I, W ) , - некоторое корневое бинарное дереводекомпозиции графа G = (V, E) ширины k. Решение подзадачи П вычисляется изтаблицы Ai, в которой сформированы все допустимые решения для подграфа G(Yj),где Y задается формулой (1). В общем случае данная таблица может содержать |Yj|столбцов (по одному столбцу на каждую вершину из Y) и q|Yi| строк (по одной накаждое допустимое решение) при условии, что q - число состояний вершины графапо отношению к допустимому решению. Тот факт, что в таблице Ai столбцами вы-ступают все вершины из Yj, обозначим через Ai(Yi ) . Аналогичным образом обозначимчерез Ai(Xi ) таблицу, содержащую допустимые решения для подграфа G(Xi ) , то естьподграфа, индуцированного вершинами только одного «мешка» Xi , и назовем её ло-кальной таблицей. Если узел i является листом, то Ai(Xi ) совпадает с Ai(Yi ) . Еслиi - внутренний узел или корень, то таблица Ai(Yi ) формируется из таблицы A i ( X i ) итаблиц узлов прямых потомков узла i путем их согласования по строкам. Такое согла-сование таблиц в реляционной алгебре выполняет естественное соединение txi (далеепросто соединение). Данная операция бинарная и отвечает законам коммутативностии ассоциативности. Поэтому общая схема формирования таблицы Ai(Yi ) для внутрен-него или корневого узла i, имеющего узлы j и l в качестве прямых потомков, можетбыть представлена рис. 3. Так как |Xi| ^ k + 1 при всех i Е I, то число столбцов всякойтаблицы Ai(Yi ) , соответствующей узлу i с двумя прямыми потомками, может дости-гать 3(k + 1 ) , а число строк в худшем случае (когда операция соединения вырождается\ в декартово произведение) -значения q 3k .Рис. 3. Созданиетаблицы для внутреннего узла путем соединенияПусть (M, T) -Kloks-дерево ширины k. Тогда для всех типов узлов |Y | ^ k + 1.Действительно, если узлу i непосредственно подчинены два узла l и j, тоX i = X i = X j , Yi = X i U X j U X i = X i , |Yi| ^ k + 1.Если i - узел-вставка с прямым потомком j, тоX j С X i , |Xi| = |Xj| + 1, Yi = X i U X j = X i , |Yi| ^ k + 1.Если i - узел-удаление с прямым потомком j , тоX i С X j , |Xi| = |Xj| - 1, Yi = X i U X j = X j , |Yi| ^ k + 1.Пусть теперь (M, T) - BfeS-дерево ширины k. В данном случае также для всехтипов узлов |Yi| ^ k + 1. Для узлов-листьев это очевидно. Рассмотрим внутренниеузлы. Заметим, что по построению BfeS-дерева узел-сепаратор s всегда имеет толькоодного родителя (согласно рис. 2 это узел i), одного прямого потомка (это узел j) иXs = Xi П Xj = 0, Xs С Xi , Xs С Xj. Поэтому для таблицы узла-сепаратора sвыполняются отношения Ys = Xs U Xj = X j , |Ys | ^ k + 1.Для узла i, играющего роль родителя узла s, справедливы подобные отношения:Y = Xi U Xs = X i , |Yi| ^ k + 1 . В BfeS-дереве любой внутренний узел i является либоузлом-сепаратором, либо родителем одного или двух узлов-сепараторов. Поэтому длянего всегда |Yi| ^ k + 1 . Значит, с точки зрения числа столбцов BfeS-дерево сопоставимос Kloks-деревом, хотя имеет в большинстве случаев меньшее число таблиц.Для Kloks-дерева и BfeS-дерева число строк создаваемых таблиц динамическогопрограммирования в худшем случае составляет O(qk). Это теоретическая оценка, иона слишком пессимистичная. На самом деле, как было ранее замечено, всякое дере-во декомпозиции (M, T ) , M = { X i : i Е I } , T = ( I , W ) , графа G = (V, E) есть нечто иное, как дерево соединений ациклического гиперграфа H = (V, M ) . Исходя изсвойств ациклических гиперграфов, совокупность таблиц Ai, i Е I, обладает монотон-ным планом соединения. Монотонный план - это такой порядок соединения таблиц,когда число строк всякой промежуточной таблицы не превышает числа строк резуль-тирующей таблицы. Монотонный план соединения отвечает обходу дерева соединенияациклического гиперграфа H = (V, M) снизу вверх (от листьев к корню), при этомв роли корня может выступать произвольный узел дерева соединений [6]. Таким об-разом, при реализации метода динамического программирования по Kloks-дереву илиBfeS-дереву ширины k в большинстве случаев лишь для таблицы корневого узла числоkстрок достигает значения qk.Исключительная особенность BfeS-дерева состоит в том, что к нему применимоеще одно свойство ациклических гиперграфов - существование программы полусоеди-нений для совокупности таблиц Ai, i Е I. Представим себе, что мы имеем реляционнуюбазу данных, состоящую из множества таблиц Ai, i Е I. Пусть эта база данных рас-пределена по узлам сети так, что в каждом узле находится только одна таблица, аконфигурация сети задана деревом T. Требуется выполнить запрос к базе данных,в котором надо соединить все таблицы Ai, i Е I. Пусть запрос сформулирован в кор-невом узле. Тогда процесс вычисления запроса сводится к последовательному соеди-нению таблиц снизу вверх по дереву T с передачей по каналам связи промежуточныхтаблиц на вышестоящий уровень узлов этой сети. Предположим, что большая частьвремени выполнения запроса приходится на время передачи данных. В этом случаеэффективность вычисления запроса зависит от минимизации объёма передаваемыхданных. В ациклических реляционных базах данных это достигается за счёт примене-ния программы полусоединений, когда вверх по дереву соединений передаются толькоте данные, которые участвуют в соединении далее. Очевидно, что процесс выполнениязапроса по дереву соединений (M, T) идентичен процессу формирования таблиц дина-мического программирования по дереву декомпозиции (M, T ) , а минимизации объёмапередаваемых данных - сокращение числа строк промежуточных таблиц динамиче-ского программирования.Поясним действия, выполняемые операцией полусоединения. Пусть заданы две таб-лицы Aj(Xi) и Aj (Xj), отвечающие узлам i и j, где узел j - прямой потомок узла i.Тогда полусоединением A j ( X i ) и Aj ( X j ) называется таблица, определяемая равенствомA j к A j = (Aj M A j ) , (2)то есть Aj к Aj - эта часть строк таблицы Aj, которая участвует в соединении состроками из Aj. По законам реляционной алгебры [6, с. 348]nXi ( A j м A j ) = nXiHXj ( A j ) м A j ; (3)A j м A j = ( A j м A j ) м A j . (4)Если Xs = Xj П X j , то из (2)-(4) следует, чтоAj M A j = n x s ( A j ) M A j , (5)где nxs ( A j ) -таблица, которая получается из Aj извлечением столбцов, входящихв X s , и удалением строк-дубликатов. Так действует операция п, называемая в реляци-онной алгебре проекцией. Эта операция неизменно уменьшает число строк и столбцовтаблицы-операнда. Заметим, что множество Xs = Xj П Xj соответствует узлу-сепара-тору s в Б&Б-дереве (рис. 2). Если таблицу для узла-сепаратора получать из таблицыпрямого его потомка, применяя операцию проекции, то, согласно (5), операцию со-единения таблиц можно осуществить более эффективно с точки зрения времени ипамяти. Узел-сепаратор играет в этом случае роль транзита, передающего вверх подереву только те данные, которые используются для формирования таблицы Ar . Такойэффект от узла-сепаратора гарантируется ацикличностью гиперграфа, ассоциирован-ного с Б&Б-деревом.5. Решение задачи о вершинном покрытии методом динамическогопрограммирования по BfcS-деревуЗадача о вершинном покрытии является типичной NP-трудной задачей на графах,к которой сводятся многие подобные задачи. Напомним, что подмножество V1 С Vобразует вершинное покрытие графа G = (V, E ) , если каждое ребро из E инцидентнохотя бы одной вершинеиз Vi . Покрытие называется минимальным, если оно не содер-жит покрытия с меньшим числом вершин, и наименьшим, если число вершин в нёмнаименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытииграфа G называется числом вершинного покрытия этого графа и обозначается ^o(G).В оптимизационной постановке данная задача формулируется следующим образом.Задан граф G = (V, E). Требуется найти число вершинного покрытия ,50(G) и наи-меньшее вершинное покрытие графа G, отвечающее ,50(G).Свойство подмножества V С V быть вершинным покрытием графа G = (V, E)выражается конечной MSOL-формулой (см. таблицу):VertexCover(Vi) ^ (Ve2)(3v3)(v3 G Vi & Incident(v3, e2)). (6)Согласно теореме Курселя, применение к данной задаче метода динамического про-граммирования по дереву декомпозиции приведёт к FPT-алгоритму при условии, чтовходному графу свойственна ограниченная древовидная ширина. Убедимся в этом.Пусть заданы граф G с tw(G) ^ k, его BfeS-дерево ( M , T ) , M = { X j : i G I },T = (I, W ) , ширины k и с узлом r в роли корня. Реализация метода динамическогопрограммирования по BfeS-дереву (M, T) предполагает конкретизацию рекуррентнойпроцедуры формирования таблиц Aj(Yj), то есть определения для каждого из четырёхтипов узлов правил, по которым вычисляются все допустимые решения подзадачи П(i G I). Дадим описание этих правил для задачи о вершинном покрытии, используяязык реляционной алгебры.Пусть имеем узел-лист i с «мешком» Xj. Для графа G(Xj) задача решается пол-ным перебором. Для этого создается таблица Aj(Yj) как A j ( X j ) по следующим пра-вилам. В этой таблице |Xj | + 1 столбцов и 2IYI строк, отдельная строка для каждогоиз 2|Xi 1 различных подмножеств Z С Xj. Состав вершин, входящих в Z, представля-ется битовой шкалой b: b(v) = 1, если вершина v G Z, и b(v) = 0 в противном случае.Столбец c ( Z ) таблицы A j ( X j ) содержит характеристику решения: c ( Z ) = |Z|, если Z -вершинное покрытие для G(Xj), иначе c ( Z ) = Является ли подмножество Z до-пустимым решением для Щ, устанавливается путём проверки на истинность значенияпредиката (6). Если да, то c ( Z ) вычисляется по формуле c ( Z ) = |Z| = YI b(v).veXiРассмотрим узел-сепаратор s с «мешком» Xs и одним прямым потомком j, кото-рый имеет «мешок» X j . В данном случае Xs С Xj С Yj, где Yj -множество вершинисходного графа G, которые принадлежат Xj и всем «мешкам» узлов, являющихсяв T потомками узла j. Пусть для узла j ранее уже была построена таблица Aj (Yj).Тогда таблица As(YS) вычисляется по формулеAs = n Q ( A j ) , (7)где п - операция проекции, которая выбирает из таблицы Aj (Yj) подмножество столб-цов Q = Xs U { c ( Z ) } . В полученной таблице возможны строки, совпадающие по бито-вым шкалам и имеющие разные значения c 1 ( Z ) , c 2 ( Z ) , . . . , c^(Z), h ^ 1. Для всех такихстрок полагаетсяc ( Z ) = m i n { c i ( Z ) , c 2 ( Z ) , . . . , Ch(Z)} (8)и в As(Ys ) оставляется только одна из них. После этого результирующая таблица As (Ys)содержит только ту информацию из Aj (Yj), которая необходима для согласования еёс таблицей вышестоящего узла. Справедливостьформул (7) и (8) вытекает из наслед-ственности свойства, представленного формулой (6): если Z - вершинное покрытиеграфа Gj = G(Yj), то множество Z П Xs С Yj является вершинным покрытием гра-фа G ( X s ).Пусть i - узел-расширение с одним прямым потомком s, для которого Xs С Xj.Предположим, что для узла s ранее уже была создана таблица As(Ys ) . В данной си-туации вначале формируется локальная таблица Aj(Xj ) , которая затем связываетсяс таблицей As(Ys ) , и результат записывается в Aj(Yj):Aj = A j м A. (9)Поскольку Xs С Xi, то, согласно (9), в Ai(Yi) войдут все столбцы из A'i(Xi) и добавитсяещё дополнительный столбец со значениями c(Z) из As(Ys ) . Пусть Ai.c(Z) и As . c ( Z ) -характеристики Z С Xi , включённые в результирующую таблицу Ai(Yi) из Ai и Asсоответственно. В этих обозначениях формула пересчёта значений c ( Z ) для Ai имеетвидc ( Z ) = Ai.c(Z) + As.c(Z) - . b(v). (10)vexsДанная формула реализует принцип включения и исключения: мощности допустимыхи согласованных между собой решений складываются и вычитается число вершин,учтённых дважды (это вершины из «мешка» узла-сепаратора). Справедливость этойформулы вытекает из наследственности свойства, представленного формулой (6).Пусть узел i имеет в качестве прямых потомков узлы-сепараторы l и j с «меш-ками» Xi и Xj соответственно. Допустим, что этим узлам отвечают таблицы Ai (Yi)и Aj (Yj), а узлу i - локальная таблица Ai(Xi ) . Сначала таблица Ai(Xi ) связывает-ся с таблицей Ai(Yi) по формулам (9), (10), а затем полученная таблица - с табли-цей Aj (Yj). Таким образом, обработка узла-соединения сводится к двукратному по-вторению действий, определённых для узла-расширения.Как только достигается корневой узел r и вычисляется таблица Ar (V), значениечисла вершинного покрытия графа G находится по формулево (G) = min{c(Z) : Z С Yr}. Г11)Построение самого вершинного покрытия выполняется при обходе всех узлов дерева Tсверху вниз (от корня к листьям) с использованием созданных ранее таблиц динами-ческого программирования. Для хранения O(n) таблиц, каждая из которых имеетразмер O(k2k) , необходима память O(k2kn). Обход дерева T с O(n) узлами можнореализовать за время O(n). Время обработки каждого узла сопоставимо с размеромсоздаваемых таблиц. Поэтому для задачи о вершинном покрытии время работы FPT-алгоритма, реализующего метод динамического программирования по Б&Б-дереву ши-рины k, составляет O(k2kn). Это полностью согласуется с оценкой, приведенной втеореме Курселя. На практике эта оценка может быть более оптимистичной за счетприменения Б&Б-дерева.Рассмотрим конкретный граф G вместе с его деревом декомпозиции (рис. 4).Рис. 4. Граф G и его оптимальное дерево декомпозиции ширины 2Соответствующее Б&Б-дерево графа G изображено на рис. 5. Найдём наименьшеевершинное покрытие заданного графа с помощью описанноговыше FPT-алгоритма.Процесс подъёма по Б&Б-дереву начнём с узла 1. Это узел-лист. Узел 2 является узлом-Рис. 5. BfeS-дерево ширины 2. Узлу с номером i отвечает «мешок» Xi, i = 1, 2,..., 7сепаратором и родителем для узла 1. Таблицы Ai и A2 отвечают узлам 1 и 2 (рис. 6,аи б). Исходя из (7), (8), A2 = ng(A1 ) , Q = { g } U { c ( Z ) } . Аналогично узлам 4 и 5 со-ответствуют таблицы A4 , A5 (рис. 6,в и г) и A5 = ng(A4 ) , Q = { y } U { c ( Z ) } . Узел 3 -это узел-объединение по отношению к узлам 2 и 5. Для него таблица A'3 (рис. 6,д) со-держит локальную информацию для подграфа G(X3 ) . Соединение A3 с таблицей A2,а затем с таблицей A5 по формулам (9) и (10) даёт A3 (рис. 6,е). Узел 6 -узел-сепа-ратор. Для него A6 = ng(A3 ) , Q = { y , w } U { c ( Z ) } (рис. 6 , ж ) . Корневой узел 7 -этоузел-расширение по отношению к узлу 6. В соответствии с формулами (9) и (10) таб-лица A7 имеет вид, представленный на рис. 6,з. Таблица A7 отвечает корневому узлу.Применение формулы (11) к A7 даёт в0 (G) = 3.Ai А2 At А59 V c(Z)0 0 000 1 11 0 11 1 2aАз'У w 9 c(Z)0 0 0 000 0 1 10 1 0 000 1 1 21 0 0 001 0 1 21 1 0 21 1 1 39 c(Z)0 11 1Аз А6 AiУ w 9 c[Z)0 0 0 000 0 1 20 1 0 000 1 1 31 0 0 001 0 1 21 1 0 31 1 1 3У и c[Z)0 0 000 1 11 0 11 1 2бA6У w c[Z)0 0 20 1 31 0 21 1 3У c(Z)0 11 1X У w c(Z)0 0 0 000 0 1 000 1 0 000 1 1 31 0 0 31 0 1 41 1 0 31 1 1 4Рис. 6. Таблицы динамического программирования для вычисления вершинного покрытияграфа с рис. 4Спуск по BfeS-дереву от корня к листьям определяет следующие наименьшие вер-шинные покрытия графа G : { x , y , g } , { x , g , u } , { y , w , g } , { y , w , v } . Заметим, что дляисходного графа допустимы деревья декомпозиции, отличные от дерева, указанногона рис. 4, а значит, и BfeS-деревья, несхожие с рассмотренным выше BfeS-деревом.Решение задачи о вершинном покрытии на их основе приведёт, возможно, к другимоптимальным решениям, хотя неизменным будет значение во (G) = 3.Очевидно, что приведённый выше FPT-алгоритм можно применять для взвешен-ной версии задачи о вершинном покрытии, а его идеи относительно правил форми-рования таблиц динамического программирования для различных типов узлов B&S-дерева - для решения других подобных графовых задач: нахождения наибольшегонезависимого множества вершин, поиска наибольшей клики, отыскания наименьше-го доминирующего множества графа. Конечно, для этих задач необходимо уточнениеформул вычисления числовых характеристик решения.ЗаключениеМетод динамического программирования на основе дерева декомпозиции - один изсовременных способов преодоления вычислительной сложности NP-трудных задач вы-бора с помощью FPT-алгоритмов. В работе предложено бинарное сепараторное дереводекомпозиции, которое обеспечивает компромисс между размером и числом таблицдинамического программирования и расширяет область практического примененияданного подхода. Реляционный взгляд на процесс динамического программирования(как процесс соединения таблиц базы данных, распределённой по узлам сети, конфи-гурация которой задаётся деревом декомпозиции) позволяет применять при решениизадач выбора свойства ациклических гиперграфов и способствует алгоритмическойконкретизации метода.

Ключевые слова

алгоритмы на графах, дерево декомпозиции, динамическое программирование, graph algorithms, tree decomposition, dynamic programming

Авторы

ФИООрганизацияДополнительноE-mail
Быкова Валентина ВладимировнаСибирский федеральный университет, г. Красноярскдоцент, кандидат технических наук, профессор Института математикиbykvalen@mail.ru
Всего: 1

Ссылки

Downey R. and Fellows M. Parameterized complexity. New York: Springer Verlag, 1999.
Быкова В. В. FPT-алгоритмы и их классификация на основе эластичности // Прикладная дискретная математика. 2011. №2(12). С. 40-48.
Bodlaender H. L. Treewidth: Algorithmic techniques and results // LNCS. 1997. V. 1295. P. 19-36.
Компьютер и задачи выбора. М.: Наука, 1989.
Быкова В. В. Вычислительные аспекты древовидной ширины графа // Прикладная дискретная математика. 2011. №3(13). С. 65-79.
Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.
Courcelle B. The monadic second-order logic of graphs. III. Tree decompositions, minors and complexity issues // RAIRO Inform. Theor. Appl. 1992. V.26(3). P. 257-286.
Bodlaender H. L. and Kloks T. Efficient and constructive algorithms for the pathwidth and treewidth of graphs // J. Algorithms. 1996. V.21. P. 358-402.
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журнал СФУ. Математика и физика. 2008. № 1(3). С. 236-246.
Aspvall B., Proskurowski A., and Telle J. A. Memory requirements for table computations in partial k-tree algorithms // Algorithmica. 2000. V. 27(3). P. 382-394.
Bodlaender H. L. and Fomin F. V. Tree decompositions with small cost // Discr. Appl. Math. 2005. V. 145(2). P. 143-154.
Kloks T. Treewidth. Computations and Approximations. Springer Verlag. LNCS. 1994. V. 842.
 FPT-алгоритмы на графах ограниченной древовидной ширины | ПДМ. 2012. № 2(16).

FPT-алгоритмы на графах ограниченной древовидной ширины | ПДМ. 2012. № 2(16).

Полнотекстовая версия