Русская Википедия:Итеративное сжатие
Итеративное сжатие — это алгоритмическая техника разработки Шаблон:Не переведено 5. В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи.
История
Технику разработали Рид, Смит и ВеттаШаблон:Sfn, чтобы показать, что Шаблон:Не переведено 5 разрешима за время <math>O(3^{k}kmn)</math> для графов с Шаблон:Mvar вершинами, Шаблон:Mvar рёбрами и числом удаляемых вершин Шаблон:Mvar. Задача об удалении нечётных циклов — это задача поиска наименьшего набора вершин, который включает по меньшей мере по одной вершине из любого нечётного цикла. Параметрическая сложность этой задачи долгое время оставалась открытойШаблон:SfnШаблон:Sfn. Позже эта техника стала очень полезна для доказательства результатов по Шаблон:Не переведено 5. Сейчас эту технику принято считать одной из фундаментальных в области параметризованных алгоритмов.
Итеративное сжатие успешно использовалось во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклов вершин, удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершинШаблон:Sfn. Метод также успешно использовался для точных алгоритмов экспоненциального времени для нахождения независимого множестваШаблон:Sfn.
Техника
Итеративное сжатие применимо, например, для параметризованных задач на графах, входом которых является граф Шаблон:Math и натуральное число Шаблон:Mvar, а задача ставится как проверка существования решения (набора вершин) размера <math>\leqslant k</math>. Предположим, что задача замкнута относительно порождённых подграфов (если решение существует для <math>\leqslant k</math> для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение Шаблон:Mvar размера <math>k + 1</math> быть сжато до меньшего решения размера Шаблон:Mvar.
Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом:
- Начинаем с подграфа, порождённого набором вершин Шаблон:Mvar размера Шаблон:Mvar и решения Шаблон:Mvar, которое равно самому Шаблон:Mvar.
- Пока <math>S \ne V</math> осуществляем следующие шаги:
- Пусть Шаблон:Mvar будет любой вершиной <math>V \backslash S</math>, добавим Шаблон:Mvar в Шаблон:Mvar
- Проверяем, можно ли решение с Шаблон:Math вершинами Шаблон:Mvar} для Шаблон:Mvar сжать до решения с Шаблон:Mvar вершинами.
- Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с Шаблон:Mvar вершинами.
- В противном случае, полагаем Шаблон:Mvar новым сжатым решением и возвращаем к началу цикла.
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть <math>f(k) \cdot n^c</math> для некоторой константы c, то процедура итеративного сжатия для решения полной задачи работает за время <math>f(k) \cdot n^{c+1}</math>. Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра Шаблон:Mvar неизвестно, оно может быть найдено с помощью внешнего уровня Шаблон:Не переведено 5 или линейного поиска для оптимального выбора Шаблон:Mvar, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия.
Приложения
В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более k вершин за время <math>O(3^kkmn)</math>. Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатиеШаблон:Sfn. Чтобы сжать удаляемое множество Шаблон:Mvar размера Шаблон:Math до множества Шаблон:Mvar размера Шаблон:Mvar их алгоритм проверяет все <math>3^{k+1}</math> разбиения множества Шаблон:Mvar на три подмножества — подмножество множества Шаблон:Mvar, которое принадлежит новому удаляемому множеству, и два подмножества множества Шаблон:Mvar, которые принадлежат двум долям двудольного графа, остающегося после удаления множества Шаблон:Mvar. Когда эти три множества выбраны, оставшиеся вершины удаляемого множества Шаблон:Mvar (если таковое существует) могут быть найдены из них, применяя алгоритм Форда — Фалкерсона.
Вершинное покрытие — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф <math>G=(V, E)</math> и натуральное число Шаблон:Mvar, а алгоритм должен решить, существует ли множество Шаблон:Mvar с Шаблон:Mvar вершинами, такое что любое ребро инцидентно вершине в Шаблон:Mvar. В варианте сжатия входом является множество Шаблон:Mvar с <math>k + 1</math> вершинами, которое инцидентно всем рёбрам графа, и алгоритм должен найти множество Шаблон:Mvar размера Шаблон:Mvar с тем же свойством, если таковое существует. Один из способов сделать это — тестируются все <math>2^{k + 1}</math> варианта, какими множество Шаблон:Mvar удаляется из покрытия и вставляется обратно в граф. Такой перебор может работать только если никакие две удаляемые вершины не смежны и для каждого такого варианта подпрограмма должна включать в покрытие все вершины вне Шаблон:Mvar инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы <math>O(2^k n^2)</math> для покрытия вершин.
См. также
- Параметрическая редукция, другая техника для фиксированно-параметрически разрешимых алгоритмов
Примечания
Литература
