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

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

История

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

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

Техника

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

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

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

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

Приложения

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

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

См. также

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