Итерационное сжатие - Iterative compression

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

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

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

Техника

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

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

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

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

Приложения

В своей оригинальной статье Reed et al. показал, как сделать граф двудольным, удалив не более k вершины во времени О(3k кмн). Позже Локшстанов, Саураб и Сикдар предложили более простой алгоритм, также использующий итеративное сжатие.[6]Для сжатия удаляемого набора Y размера k + 1 в набор для удаления Икс размера k, их алгоритм проверяет все 3k+1 перегородки Y на три подмножества: подмножество Y который принадлежит новому набору удаления, и два подмножества Y принадлежащие двум сторонам двудольного графа, который остается после удаления Икс. После выбора этих трех наборов оставшиеся вершины удаляемого набора Икс (если он существует) можно найти по ним, применив макс. расход мин. обрезка алгоритм.

Крышка Vertex - еще один пример, для которого можно использовать итеративное сжатие. В задаче о вершинном покрытии граф грамм = (V,E) и натуральное число k берутся в качестве входных данных, и алгоритм должен решить, существует ли набор Икс из k вершины такие, что каждое ребро инцидентно вершине в Икс. В компрессионном варианте задачи входом является набор Y из k + 1 вершин, инцидентных всем ребрам графа, и алгоритм должен найти набор Икс размера k с таким же свойством, если оно существует. Один из способов сделать это - проверить все 2k + 1 выбор какого подмножества Y снимается с крышки и снова отображается на графике. Такой выбор может работать только в том случае, если никакие две удаленные вершины не являются смежными, и для каждого такого выбора подпрограмма должна включать в покрытие все вершины вне Y которые инцидентны кромке, которая становится открытой в результате этого удаления. Использование этой подпрограммы в алгоритме итеративного сжатия дает простой О(2k п2) алгоритм вершинного покрытия.

Смотрите также

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

Рекомендации

  1. ^ Рид, Брюс; Смит, Кейли; Ветта, Адриан (2004), "Нахождение трансверсалей нечетного цикла", Письма об исследованиях операций, 32 (4): 299–301, Дои:10.1016 / j.orl.2003.10.009, МИСТЕР  2057781.
  2. ^ Нидермайер, Рольф, Приглашение к алгоритмам с фиксированными параметрами, Oxford University Press, стр. 184, г. ISBN  9780198566076
  3. ^ Циган, Марек; Фомин, Федор В .; Ковалик, Лукаш; Локштанов Даниил; Маркс, Даниил; Пилипчук, Марцин; Пилипчук, Михал; Саураб, Сакет (2015). Параметризованные алгоритмы. Springer. п. 555. ISBN  978-3-319-21274-6..
  4. ^ Го, Цзюн; Мозер, Ханнес; Нидермайер, Рольф (2009), "Итерационное сжатие для точного решения NP-трудных задач минимизации", Алгоритмика больших и сложных сетей, Конспект лекций по информатике, 5515, Springer, стр. 65–80, Дои:10.1007/978-3-642-02094-0_4, ISBN  978-3-642-02093-3.
  5. ^ Фомин, Федор; Гасперс, Серж; Крач, Дитер; Лидлофф, Матье; Саураб, Сакет (2010), «Итеративное сжатие и точные алгоритмы», Теоретическая информатика, 411 (7): 1045–1053, Дои:10.1016 / j.tcs.2009.11.012.
  6. ^ Локштанов Даниил; Саураб, Сакет; Сикдар, Сомнатх (2009), «Более простой параметризованный алгоритм для ОКТ», 20-й Международный семинар по комбинаторным алгоритмам, IWOCA 2009, Градец-над-Моравици, Чешская Республика, 28 июня - 2 июля 2009 г., Отредактированные избранные статьи, Конспект лекций по информатике, 5874, Springer, стр. 380–384, Дои:10.1007/978-3-642-10217-2_37, ISBN  978-3-642-10216-5.