Итеративное сжатие

Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов^[англ.]. В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи.

История

Технику разработали Рид, Смит и Ветта^[1], чтобы показать, что задача об удалении нечётных циклов^[англ.] разрешима за время ${\displaystyle O(3^{k}kmn)}$ для графов с n вершинами, m рёбрами и числом удаляемых вершин k. Задача об удалении нечётных циклов — это задача поиска наименьшего набора вершин, который включает по меньшей мере по одной вершине из любого нечётного цикла. Параметрическая сложность этой задачи долгое время оставалась открытой^[2][3]. Позже эта техника стала очень полезна для доказательства результатов по фиксированно-параметрической разрешимости^[англ.]. Сейчас эту технику принято считать одной из фундаментальных в области параметризованных алгоритмов.

Итеративное сжатие успешно использовалось во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклов вершин, удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин^[4]. Метод также успешно использовался для точных алгоритмов экспоненциального времени для нахождения независимого множества^[5].

Техника

Итеративное сжатие применимо, например, для параметризованных задач на графах, входом которых является граф G=(V,E) и натуральное число k, а задача ставится как проверка существования решения (набора вершин) размера ${\displaystyle \leqslant k}$. Предположим, что задача замкнута относительно порождённых подграфов (если решение существует для ${\displaystyle \leqslant k}$ для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение Y размера ${\displaystyle k+1}$ быть сжато до меньшего решения размера k.

Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом:

1. Начинаем с подграфа, порождённого набором вершин S размера k и решения X, которое равно самому S.
2. Пока ${\displaystyle S\neq V}$ осуществляем следующие шаги:
   • Пусть v будет любой вершиной ${\displaystyle V\backslash S}$, добавим v в S
   • Проверяем, можно ли решение с (k + 1) вершинами Y=X ∪ {x} для S сжать до решения с k вершинами.
   • Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с k вершинами.
   • В противном случае, полагаем X новым сжатым решением и возвращаем к началу цикла.

Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть ${\displaystyle f(k)\cdot n^{c}}$ для некоторой константы c, то процедура итеративного сжатия для решения полной задачи работает за время ${\displaystyle f(k)\cdot n^{c+1}}$. Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра k неизвестно, оно может быть найдено с помощью внешнего уровня экспоненциального поиска^[англ.] или линейного поиска для оптимального выбора k, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия.

Приложения

В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более k вершин за время ${\displaystyle O(3^{k}kmn)}$. Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие^[6]. Чтобы сжать удаляемое множество Y размера k + 1 до множества X размера k их алгоритм проверяет все ${\displaystyle 3^{k+1}}$ разбиения множества Y на три подмножества — подмножество множества Y, которое принадлежит новому удаляемому множеству, и два подмножества множества Y, которые принадлежат двум долям двудольного графа, остающегося после удаления множества X. Когда эти три множества выбраны, оставшиеся вершины удаляемого множества X (если таковое существует) могут быть найдены из них, применяя алгоритм Форда — Фалкерсона.

Вершинное покрытие — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф ${\displaystyle G=(V,E)}$ и натуральное число k, а алгоритм должен решить, существует ли множество X с k вершинами, такое что любое ребро инцидентно вершине в X. В варианте сжатия входом является множество Y с ${\displaystyle k+1}$ вершинами, которое инцидентно всем рёбрам графа, и алгоритм должен найти множество X размера k с тем же свойством, если таковое существует. Один из способов сделать это — тестируются все ${\displaystyle 2^{k+1}}$ варианта, какими множество Y удаляется из покрытия и вставляется обратно в граф. Такой перебор может работать только если никакие две удаляемые вершины не смежны и для каждого такого варианта подпрограмма должна включать в покрытие все вершины вне Y инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы ${\displaystyle O(2^{k}n^{2})}$ для покрытия вершин.

См. также

• Параметрическая редукция, другая техника для фиксированно-параметрически разрешимых алгоритмов