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

История

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

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

Техника

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

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

Приложения

В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более k вершин за время ${\displaystyle O(3^{k}kmn)}$ . Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие . Чтобы сжать удаляемое множество 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})}$ для покрытия вершин.

См. также

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

Примечания

Литература

• Bruce Reed, Kaleigh Smith, Adrian Vetta. Finding odd cycle transversals // Operations Research Letters. — 2004. — Т. 32 , вып. 4 . — doi : .
• Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. — Oxford University Press, 2006. — Т. 31. — (Oxford lecture series in mathematics and its applications). — ISBN 9780198566076 .
• Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Parameterized Algorithms. — Springer, 2015. — ISBN 978-3-319-21274-6 .
• Jiong Guo, Hannes Moser, Rolf Niedermeier. Iterative compression for exactly solving NP-hard minimization problems // Algorithmics of Large and Complex Networks. — Springer, 2009. — Т. 5515. — С. 65–80. — (Lecture Notes in Computer Science). — ISBN 978-3-642-02093-3 . — doi : .
• Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh. Iterative compression and exact algorithms // Theoretical Computer Science. — 2010. — Т. 411 , вып. 7 . — С. 1045–1053 . — doi : .
• Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar. Simpler parameterized algorithm for OCT // 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers. — Springer, 2009. — Т. 5874. — С. 380–384. — (Lecture Notes in Computer Science). — ISBN 978-3-642-10216-5 . — doi : .