Итеративное сжатие

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

История

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

Итеративное сжатие успешно использовалось во многих задачах, например для удаления нечётных циклов (см. ниже) и удаления рёбер для получения двудольности, нахождения разрезающих циклов вершин, удаления кластерных вершин и нахождения разрезающих ориентированных циклов вершин[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 сжать до решения с 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)}$. Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие[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})}$ для покрытия вершин.

См. также

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

Примечания

1. Reed, Smith, Vetta, 2004, с. 299–301.
2. Niedermeier, 2006, с. 184.
3. Cygan, Fomin, Kowalik и др., 2015, с. 555.
4. Guo, Moser, Niedermeier, 2009, с. 65–80.
5. Fomin, Gaspers, Kratsch и др., 2010, с. 1045–1053.
6. Lokshtanov, Saurabh, Sikdar, 2009, с. 380–384.

Литература

• Bruce Reed, Kaleigh Smith, Adrian Vetta. Finding odd cycle transversals // Operations Research Letters. — 2004. — Т. 32, вып. 4. — doi:10.1016/j.orl.2003.10.009.
• 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:10.1007/978-3-642-02094-0_4.
• Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh. Iterative compression and exact algorithms // Theoretical Computer Science. — 2010. — Т. 411, вып. 7. — С. 1045–1053. — doi:10.1016/j.tcs.2009.11.012.
• 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:10.1007/978-3-642-10217-2_37.