Итеративное сжатие — это алгоритмическая техника разработки . В данной технике на каждом шаге в задачу добавляется один элемент (такой как вершина графа), а перед его добавлением находится небольшое решение задачи.
История Технику разработали Рид, Смит и Ветта, чтобы показать, что разрешима за время для графов с вершинами, рёбрами и числом удаляемых вершин . Задача об удалении нечётных циклов — это задача поиска наименьшего набора вершин, который включает по меньшей мере по одной вершине из любого нечётного цикла. Параметрическая сложность этой задачи долгое время оставалась открытой. Позже эта техника стала очень полезна для доказательства результатов по . Сейчас эту технику принято считать одной из фундаментальных в области параметризованных алгоритмов.
Итеративное сжатие успешно использовалось во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклов вершин, удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин. Метод также успешно использовался для точных алгоритмов экспоненциального времени для нахождения независимого множества.
Техника Итеративное сжатие применимо, например, для параметризованных задач на графах, входом которых является граф и натуральное число , а задача ставится как проверка существования решения (набора вершин) размера . Предположим, что задача замкнута относительно порождённых подграфов (если решение существует для для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение размера быть сжато до меньшего решения размера .
Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом: Начинаем с подграфа, порождённого набором вершин размера и решения , которое равно самому . Пока осуществляем следующие шаги: Пусть будет любой вершиной , добавим в Проверяем, можно ли решение с вершинами } для сжать до решения с вершинами. Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с вершинами. В противном случае, полагаем новым сжатым решением и возвращаем к началу цикла.
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть для некоторой константы c, то процедура итеративного сжатия для решения полной задачи работает за время . Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра неизвестно, оно может быть найдено с помощью внешнего уровня или линейного поиска для оптимального выбора , с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия.
Приложения В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более k вершин за время . Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие. Чтобы сжать удаляемое множество размера до множества размера их алгоритм проверяет все разбиения множества на три подмножества — подмножество множества , которое принадлежит новому удаляемому множеству, и два подмножества множества , которые принадлежат двум долям двудольного графа, остающегося после удаления множества . Когда эти три множества выбраны, оставшиеся вершины удаляемого множества (если таковое существует) могут быть найдены из них, применяя алгоритм Форда — Фалкерсона.
Вершинное покрытие — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф и натуральное число , а алгоритм должен решить, существует ли множество с вершинами, такое что любое ребро инцидентно вершине в . В варианте сжатия входом является множество с вершинами, которое инцидентно всем рёбрам графа, и алгоритм должен найти множество размера с тем же свойством, если таковое существует. Один из способов сделать это — тестируются все варианта, какими множество удаляется из покрытия и вставляется обратно в граф. Такой перебор может работать только если никакие две удаляемые вершины не смежны и для каждого такого варианта подпрограмма должна включать в покрытие все вершины вне инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы для покрытия вершин.
См. также Параметрическая редукция, другая техника для фиксированно-параметрически разрешимых алгоритмов
Примечания
Литература
Категория:Алгоритмы на графах Категория:Параметрическая сложность Категория:Анализ алгоритмов