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

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

История

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

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

Техника

Итеративное сжатие применимо, например, для параметризованных задач на графах, входом которых является граф G=(V,E) и натуральное число k, а задача ставится как проверка существования решения (набора вершин) размера . Предположим, что задача замкнута относительно порождённых подграфов (если решение существует для для данного графа, то решение этого размера или меньшего существует для любого порождённого подграфа) и что существует эффективная процедура, которая определяет, может ли решение Y размера быть сжато до меньшего решения размера k.

Если это предположение выполняется, то задача может быть решена путём добавления вершин по одной за раз и нахождения решения для порождённого подграфа следующим образом:

  1. Начинаем с подграфа, порождённого набором вершин S размера k и решения X, которое равно самому S.
  2. Пока осуществляем следующие шаги:
    • Пусть v будет любой вершиной , добавим v в S
    • Проверяем, можно ли решение с (k + 1) вершинами Y=X {x} для S сжать до решения с k вершинами.
    • Если решение не может быть сжато, прерываем алгоритм — входной граф не имеет решения с k вершинами.
    • В противном случае, полагаем X новым сжатым решением и возвращаем к началу цикла.

Этот алгоритм вызывает подпрограмму сжатия линейное число раз. Поэтому, если вариант сжимающей процедуры работает за фиксированно-параметрически разрешимое время, то есть для некоторой константы c, то процедура итеративного сжатия для решения полной задачи работает за время . Ту же самую технику можно применять для нахождения множеств рёбер для свойств графов, замкнутых относительно подграфов (отличных от порождённого подграфа) или других свойств в теории графов. Когда значение параметра k неизвестно, оно может быть найдено с помощью внешнего уровня экспоненциального поиска или линейного поиска для оптимального выбора k, с поиском на каждом шаге, основываясь на том же алгоритме итеративного сжатия.

Приложения

В оригинальной статье Рид, Смит и Ветта показали, как сделать граф двудольным путём удаления не более k вершин за время . Позднее Локштанов, Саурабх и Сикдар дали более простой алгоритм, также использующий итеративное сжатие[6]. Чтобы сжать удаляемое множество Y размера k + 1 до множества X размера k их алгоритм проверяет все разбиения множества Y на три подмножества — подмножество множества Y, которое принадлежит новому удаляемому множеству, и два подмножества множества Y, которые принадлежат двум долям двудольного графа, остающегося после удаления множества X. Когда эти три множества выбраны, оставшиеся вершины удаляемого множества X (если таковое существует) могут быть найдены из них, применяя алгоритм Форда — Фалкерсона.

Вершинное покрытие — это другой пример, для которого может быть применено итеративное сжатие. В задаче вершинного покрытия в качестве входных данных даётся граф и натуральное число k, а алгоритм должен решить, существует ли множество X с k вершинами, такое что любое ребро инцидентно вершине в X. В варианте сжатия входом является множество Y с вершинами, которое инцидентно всем рёбрам графа, и алгоритм должен найти множество X размера k с тем же свойством, если таковое существует. Один из способов сделать это — тестируются все варианта, какими множество Y удаляется из покрытия и вставляется обратно в граф. Такой перебор может работать только если никакие две удаляемые вершины не смежны и для каждого такого варианта подпрограмма должна включать в покрытие все вершины вне Y инцидентные ребру, которое становится непокрытым при этом удалении. Использование такой подпрограммы в алгоритме итеративного сжатия даёт простой алгоритм со временем работы для покрытия вершин.

См. также

Примечания

Литература

  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.