Эффективные алгоритмы поиска ориентированных ациклических подграфов больше гарантированных размеров

Введение 3
Постановка задачи 5
1. Предварительные сведения 6
1.1. Общие обозначения 6
1.2. Параметризованная сложность 6
1.3. Рассматриваемые гарантии 8
2. Полученные результаты 9
3. Решение для гарантии Weighted Half 10
3.1. Переформулировка задачи 10
3.2. Profit: определение и некоторые свойства 11
3.3. Основная часть решения 15
3.3.1 Элиминация противоположнонаправленных рёбер ... 15
3.3.2 Ограничение на размер вершинного покрытия. Базовая
версия FPT алгоритма 16
3.3.3 Улучшенная версия FPT алгоритма. Построение ядра,
содержащего не более 6k вершин 19
4. Решение для гарантии Unweighted Spanning Forest 25
4.1. Правила редукции 26
4.2. Оценка времени работы 33
5. Результаты для гарантии Weighted Spanning Forest 35
5.1. Решение для случая, когда MST — максимальный по вклю­чению ациклический подграф 35
5.2. Решение для случая k =1 40
Заключение 41
Список литературы 42
Купить

Ориентированные ациклические графы являются важным объектом в математике и программировании (в том числе и в прикладных задачах) — например, они используются в теории расписаний, генеологии, байесовских сетях, при разрешении взаимных блокировок, а также для преференциального голосования.
При работе с ориентированными графами довольно часто возникает естественная задача: найти максимальный (по количеству рёбер или суммар­ному весу) ациклический подграф G' заданного графа G. В 1972 году Ричард Карп доказал, что эта задача NP-трудна (а значит, если верна гипотеза о том, что P = NP, то не существует полиномиального алгоритма для её решения).
Следующим логичным шагом при исследовании данной задачи стал во­прос о её параметризованной сложности, а именно о построении эффективно­го алгоритма, который бы отвечал на вопрос о существовании ациклического подграфа G' С G, в котором хотя бы к рёбер за время, зависящее не только от размера графа, но и от параметра к. Однако существует довольно простой аргумент, объясняющий, почему эта задача лежит в классе FPT (то есть мо­жет быть решена за время |G|O(1) • f (к) для некоторой вычислимой функции f): если к < 1E(G), то требуемый подграф G всегда существует, для его построения достаточно зафиксировать некоторый порядок вершин и выбрать либо все рёбра, ведущие от меньшей вершине к большей относительно этого порядка, либо наоборот все рёбра, ведущие от большей вершине к меньшей.
Отсюда видно, что естественный способ параметризации (когда пара­метр к задаёт требуемое количество рёбер, либо их суммарный вес) — не са­мый удачный для данной задачи, так как для достаточно маленьких значений к вопроса о существовании соответствующих этим значениям ациклических подграфов в принципе не стоит. Похожая ситуация наблюдалась и во многих других задачах, поэтому в 2009 году вышла статья про параметризации для задач с нетривиальной нижней или верхней оценкой на ответ. Среди про­чего, авторы сформулировали несколько открытых задач, одна из которых как раз касается ориентированных ациклических подграфов. В ней требу­ется построить эффективный (работающий за время |G|O(1) • f (k) или хотя бы за O(|G|f(k))) параметризованный алгоритм, который бы по входу (G, k) определял, существует ли ациклический ориентированный подграф G с G, в котором хотя бы 2E(G) | + k рёбер.
Ответ не заставил себя ждать — уже в 2011 году вышла работа, в которой приводился FPT алгоритм для решения даже более общей (взвешен­ной) версии этой задачи за время |G|O(1) • 212k2.
Однако на этом исследования задачи о поиске ациклических подгра­фов больше гарантированных размеров не закончились: для ориентированных графов без циклов длины 2 известна более точная нижняя оценка на макси­мальное количество рёбер в ациклическом подграфе, а именно E(2G)I + |V(ср-1). Данная оценка задаёт ещё один способ параметризации задачи. Для этого способа тоже был получен FPT-алгоритм с временем работы (12k)! • |G|O(1).
Как видно, асимптотика всех полученных алгоритмов содержит в себе довольно большую функцию от параметра k. Таким образом, можно выделить два наиболее очевидных пути для дальнейших исследований задачи об ацик­лических подграфах в контексте параметризованной сложности: построение более эффективных с точки зрения временной сложности алгоритмов для уже рассмотренных ранее способов параметризации, а также попытка получить эффективный алгоритм для некоторых новых способов параметризации. В своей работе я поочерёдно обращаюсь и к тому, и к другому пути.
Купить