WikiSort.ru - Не сортированное

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

История

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

Итеративное сжатие испльзовалось успешно во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклы вершин, удаления кластерных вершин и нахождения разрезающих ориентированные циклы вершин^[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 сжатm до решения с k вершинами.
   • Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с k вершинами.
   • В противном случае, полагаем X новым сжатым решением и возвращаем к началу цикла.

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

Приложения

В оригинальной статье Рид Reed, Смит и Ветта показали, как сделать граф двудольным путём удаления не более 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})}$ для покрытия вершин.

См. также

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.