Methods for designing FPT-algorithms on graphs of limited treewidth.pdf Параметризированный подход к оценке сложности вычислений - естественныйспособ справиться с трудноразрешимостью задач, которые охарактеризованы какNP-трудные в соответствии с классической дихотомией P против NP [1]. Основнаяидея параметризированного подхода состоит в том, чтобы с помощью некоторого чис-лового параметра учесть структуру исходных данных и выделить основной источ-ник трудноразрешимости задачи. Параметризированный подход позволяет исследо-вать различные параметризации одной и той же задачи, каждая из которых можетприводить или не приводить к FPT-алгоритмам. Такие алгоритмы представляют ин-терес для алгоритмической практики, так как при ограниченном значении параметравремя их выполнения полиномиально зависит от длины входа алгоритма [2].В настоящее время уже известны некоторые специальные методы проектирова-ния FPT-алгоритмов для задач, решение которых ищется в конечной области [3, 4].При этом поиск решения подразумевает нахождение одного из допустимых решений(в задачах разрешения и удовлетворения ограничений) или поиск оптимального допу-стимого решения (в задачах комбинаторной оптимизации). Такие задачи в литературечасто называют задачами выбора. Большинство этих задач формулируются непосред-ственно как задачи на графах. Другие допускают графовое представление.В работе рассматриваются три наиболее цитируемых метода разработки FPT-алго-ритмов для задач выбора: параметрическая редукция (kernelization), поиск по деревуи метод динамического программирования на основе дерева декомпозиции. Суть мето-да параметрической редукции состоит в полиномиальном по времени преобразованиикаждого экземпляра ( / i , k i ) параметризированной задачи П в экземпляр (I2,k2) этойзадачи так, что k2 < ki . Результатом выполнения редукции является экземпляр (12, k2)задачи П, называемый ядром. К ядру применяется полный перебор или какой-либодругой точный метод решения. Известно [1], что параметризированная задача являет-ся FPT-разрешимой относительно некоторого параметра тогда и только тогда, когдаона может быть редуцирована по этому параметру на основе конечного набора правилредукции. Например, для задачи о вершинном покрытии со стандартным парамет-ром k (размером покрытия) редукция сводится к многократному применению двухправил: удаление изолированной вершины без изменения значения параметра k; уда-ление вершины, степень которой больше k, и уменьшение параметра k на единицу.Преимущество метода параметрической редукции состоит в том, что он легко про-граммируется, а трудность - нужно располагать набором правил редукции, которыеспецифичны для каждой отдельной задачи.Другой известный метод построения FPT-алгоритмов - это поиск по дереву. Сутьметода [4]: выделение конечного пространства поиска, размер которого зависит толькоот значения параметра, и представление этого пространства в виде дерева. При по-строении дерева поиска надо располагать правилом выделения узлов-потомков. Такиеправила, конечно же, характерны для каждой решаемой задачи выбора. Например,для задачи о вершинном покрытии графа G = (V, E) со стандартным параметром kсоздается бинарное корневое дерево поиска высоты k. Корню этого дерева приписыва-ются в качестве метки множество Z = 0 и граф G' = G. Затем в графе G' выбираетсянекоторое ребро e = {u, v}. Очевидно, что всякое вершинное покрытие для G содержитлибо вершину u, либо вершину v. Исходя из этого, корневой узел порождает два узла-потомка, первый из них получает метку Z = Z U {u} и G' = G' - u, а второй - меткуZ = Z U { v } и G' = G' - v. Далее этот процесс повторяется для каждого вновь создан-ного узла. Таким образом, формируемые в метках узлов множества Z представляютсобой возможные вершинные покрытия, а графы - то, что остается от G' для дальней-шего рассмотрения. На каждом уровне дерева поиска размер возможных вершинныхпокрытий увеличивается ровно на единицу. Любому узлу, который маркирован безре-берным графом G', приписывается множество Z, определяющее вершинное покрытиеграфа G'. Следовательно, если на высоте не более чем k возникает узел с безребер-ным графом G', то искомое вершинное покрытие - вершинное покрытие размером неболее k - найдено, в противном случае такого покрытия для графа G не существует.Алгоритм поиска по дереву затрачивает на свою работу O(n2k) времени, где n = |V|,и потому является FPT-алгоритмом относительно параметра k.Следует отметить, что методы параметрической редукции и поиска по дереву, во-обще говоря, реализуют традиционные стратегии разработки алгоритмов: первый изних воплощает принцип «уменьшай и властвуй», а второй - «разделяй и властвуй».Особенность лишь в том, что здесь они нацелены на получение FPT-алгоритмов. Ос-новной недостаток этих методов - сильная привязка к специфике решаемых задач.Наиболее универсальный метод разработки FPT-алгоритмов для задач выбора -метод динамического программирования на основе дерева декомпозиции, авторомкоторого считается Г. Бодлаендер [3]. Данный метод - сочетание декомпозиционно-го подхода к решению задачи выбора с декомпозиционным представлением входногографа, когда выделение подзадач и построение их решений осуществляется, исходяиз этого представления. Дерево декомпозиции графа - это специальная конструкция,которая описывает структуру графа «с точностью до клик и сепараторов» и опреде-ляет его древовидную ширину [5]. Метод динамического программирования на основедерева декомпозиции приводит к FPT-алгоритму, если проверяемое свойство графавыражено в виде конечной формулы монадической логики второго порядка и входнойграф имеет ограниченную древовидную ширину [6]. В работе подробно исследованэтот метод и установлено, что, несмотря на теоретическую привлекательность, прак-тическое его применение ограничивается двумя существующими проблемами, перваяиз них связана с высокими потребностями в памяти получаемых FPT-алгоритмов, авторая - с вычислением древовидной ширины и построением дерева декомпозиции.В данной работе предложено проблему памяти решать с помощью бинарного сепара-торного дерева декомпозиции (Б&Б-дерева), которое обеспечивает компромисс междуразмером и числом таблиц динамического программирования.Корневое дерево декомпозиции (M, T), M = { X j : i Е I } , T = (I, W), графа G на-зывается Б&Б-деревом, если в нем каждый узел имеет не более двух прямых потомкови относится к одному из четырех типов узлов:1) узел-лист - узел, у которого нет потомков;2) узел-сепаратор - узел s с одним прямым потомком j и узлом i в роли родителя.Всегда Xs - сепаратор графа G и Xs = Xj П Xj = 0, Xs С Xj, Xs С Xj;3) узел-расширение - узел i с одним прямым потомком s. В данном случаеX s С X i ;4) узел-соединение - узел i с двумя прямыми потомками l и j. Здесь X^ U Xj С Xj.В работе доказано, что всякое фундаментальное дерево декомпозиции n -вершинно-го графа, имеющее ширину k и O(n) узлов, может быть преобразовано за время O(n)в Б&Б-дерево, которое обладает той же шириной и O(n) узлами. Теоретически обос-нованы следующие достоинства Б&Б-дерева: переход от бинарного корневого деревадекомпозиции к Б&Б-дереву увеличивает число таблиц не более чем в два раза; B&S-дерево позволяет удерживать размер всякой таблицы динамического программирова-ния в пределах оценки O(kqk), где q - число состояний, в которых может находитьсявершина графа по отношению к возможному решению. Кроме того, для вычислениятаблиц динамического программирования по BfeS-дереву возможно привлечение ап-парата реляционной алгебры и свойств ациклических баз данных. Это способствуеталгоритмической конкретизации метода и сокращению числа строк в промежуточ-ных таблицах (за счет использования монотонного плана соединения и программыполусоединений таблиц). Приведена демонстрация применения метода динамическогопрограммирования по BfeS-дереву при решении оптимизационных задач (на приме-ре задачи о вершинном покрытии) и задач удовлетворения ограничений (на примерезадачи SAT).Подробное изложение представленных результатов можно найти в [7].

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