Итеративное сжатие
В информатике ) и небольшое решение предшествующей проблемы . итеративное сжатие — это алгоритмический метод разработки управляемых алгоритмов с фиксированными параметрами один элемент (например, вершина графа , в котором на каждом этапе к проблеме добавляется дополнение используется, чтобы помочь найти небольшое решение проблемы после шага.
Технику изобрели Рид, Смит и Ветта. [1] показать, что задача трансверсации нечетного цикла разрешима за время O (3 к kmn ) для графа с n вершинами, m ребрами и нечетным числом трансверсальности цикла k . Трансверсаль нечетного цикла — это задача поиска наименьшего набора вершин графа, включающего хотя бы одну вершину из каждого нечетного цикла; его параметризованная сложность долгое время была открытым вопросом. [2] [3] Позже этот метод оказался очень полезным для демонстрации результатов управляемости с фиксированными параметрами . Сейчас это считается одним из фундаментальных методов в области параметризованной алгоритмики.
Итеративное сжатие успешно использовалось во многих задачах, например, трансверсализация нечетного цикла (см. ниже) и раздвоение ребер , набор вершин обратной связи , удаление вершин кластера и набор вершин направленной обратной связи. [4] Он также успешно использовался для алгоритмов точного экспоненциального времени для независимого множества . [5]
Техника
[ редактировать ]Итеративное сжатие применяется, например, к параметризованным задачам на графах , входными данными которых являются граф G = ( V , E ) и натуральное число k , и где задача состоит в том, чтобы проверить существование решения (набора вершин) размера ≤ к . Предполагать что проблема имеет следующие свойства:
- Он замкнут относительно индуцированных подграфов : если решение размера ≤ k существует в данном графе, то решение этого размера или меньше также существует в каждом индуцированном подграфе).
- Если X — решение, а X’ — множество вершин, содержащих X , то X’ также является решением.
- Существует эффективная подпрограмма, которая по решению Y размера k + 1 определяет, можно ли его сжать до решения размера k . То есть он находит решение размера k или определяет, что такого решения не существует.
Если эти предположения выполняются, то проблему можно решить, добавляя вершины по одной в индуцированный подграф и находя решение индуцированного подграфа следующим образом:
- Начните с подграфа, индуцированного множеством вершин S размера k и решением X , равным S. самому (Если X не является решением S , то решения не существует.)
- Пока S ≠ V , выполните следующие действия:
- Пусть v — любая вершина V \ S и добавьте v к S
- Проверьте, ( k + 1) -вершинное решение Y = X ∪ {v } в S можно ли сжать до решения с k -вершиной.
- Если его невозможно сжать, прервите алгоритм: входной граф не имеет решения с k -вершиной.
- В противном случае установите X в новое сжатое решение и продолжите цикл.
Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Следовательно, если вариант сжатия разрешим за приемлемое время с фиксированным параметром, т. е. f ( k ) · n с для некоторой константы c процедура итерационного сжатия, решающая всю задачу, выполняется за f ( k ) · n с +1 время. Тот же метод можно применить для поиска наборов ребер для свойств графа, замкнутых относительно подграфов (а не для индуцированных подграфов), или для других свойств, выходящих за рамки теории графов. Когда значение параметра k неизвестно, его можно найти с помощью внешнего уровня экспоненциального поиска или последовательного поиска оптимального выбора k , причем каждый шаг поиска основан на одном и том же алгоритме итеративного сжатия.
Приложения
[ редактировать ]В своей оригинальной статье Reed et al. показал, как сделать граф двудольным, удалив не более k вершин за время O (3 к кмн ). Позже Локшстанов, Саураб и Сикдар предложили более простой алгоритм, также использующий итеративное сжатие. [6] Чтобы сжать набор удалений Y размера k + 1 до набора удалений X размера k , их алгоритм проверяет все 3 к +1 разделяет Y на три подмножества: подмножество Y , принадлежащее новому множеству удаления, и два подмножества Y , принадлежащие двум сторонам двудольного графа, который остается после удаления X . После того, как эти три набора выбраны, оставшиеся вершины набора удаления X (если он существует) могут быть найдены из них, применив алгоритм минимального разреза с максимальным потоком .
Покрытие вершин — еще один пример, для которого можно использовать итеративное сжатие. В задаче о покрытии вершин граф G = ( V , E ) и натуральное число k принимаются в качестве входных данных, и алгоритм должен решить, существует ли набор из k вершин , такой, что каждое ребро инцидентно вершине из X. X В варианте задачи со сжатием входными данными является набор Y из k + 1 вершин, инцидентных всем ребрам графа, и алгоритм должен найти набор X размера k с тем же свойством, если он существует. Один из способов сделать это — протестировать все 2 к + 1 выбор того, какое подмножество Y следует удалить из обложки и снова ввести в граф. Такой выбор может работать только в том случае, если никакие две удаленные вершины не являются соседними, и для каждого такого выбора подпрограмма должна включать в покрытие все вершины вне Y , инцидентные ребру, которое становится непокрытым в результате этого удаления. Использование этой подпрограммы в алгоритме итеративного сжатия дает простой результат O (2 к н 2 ) алгоритм вершинного покрытия.
См. также
[ редактировать ]- Кернелизация , другой метод проектирования управляемых алгоритмов с фиксированными параметрами.
Ссылки
[ редактировать ]- ^ Рид, Брюс ; Смит, Кейли; Ветта, Адриан (2004), «Нахождение трансверсалей нечетного цикла», Operations Research Letters , 32 (4): 299–301, doi : 10.1016/j.orl.2003.10.009 , MR 2057781 .
- ^ Нидермейер, Рольф , Приглашение к алгоритмам с фиксированными параметрами , Oxford University Press, стр. 184, ISBN 9780198566076
- ^ Сайган, Марк; Фомин Федор Владимирович; Ковалик, Лукаш; Локштанов Даниил; Маркс, Дэниел; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015), Параметризованные алгоритмы , Springer, стр. 555, ISBN. 978-3-319-21274-6 .
- ^ Го, Цзюн; Мозер, Ханнес; Нидермайер, Рольф (2009), «Итеративное сжатие для точного решения NP-трудных задач минимизации», Алгоритмика больших и сложных сетей , Конспекты лекций по информатике, том. 5515, Springer, стр. 65–80, номер документа : 10.1007/978-3-642-02094-0_4 , ISBN. 978-3-642-02093-3 .
- ^ Фомин, Федор; Гасперс, Серж; Крач, Дитер; Лидлофф, Матье; Саураб, Сакет (2010), «Итеративное сжатие и точные алгоритмы», Theoretical Computer Science , 411 (7): 1045–1053, doi : 10.1016/j.tcs.2009.11.012 .
- ^ Локштанов Даниил; Саураб, Сакет; Сикдар, Сомнат (2009), «Упрощенный параметризованный алгоритм для OCT», 20-й Международный семинар по комбинаторным алгоритмам, IWOCA 2009, Градец-над-Моравичи, Чешская Республика, 28 июня – 2 июля 2009 г., Переработанные избранные статьи , Конспекты лекций по информатике, том. 5874, Springer, стр. 380–384, номер doi : 10.1007/978-3-642-10217-2_37 , ISBN. 978-3-642-10216-5 .