Точные алгоритмы построения доминирующего множества: различия между версиями

Алгоритмическая сложность задачи построения минимального доминирующего множества и ее модификаций при ограничении входных данных графами определенного класса широко изучалась в литературе (см., например, [10]). В частности, известно, что эта задача остается NP-полной на двудольных графах, расщепляемых графах, планарных графах и графах со степенью не выше трех. Существуют алгоритмы с полиномиальным временем исполнения для вычисления минимального доминирующего множества – в частности, для перестановочных, интервальных и k-полигональных графов. Существует также алгоритм с временной сложностью <math>O(4^k n^{O(1)}) \; </math>, способный построить минимальное доминирующее множество на графах с [[древесная ширина графа|древесной шириной]] не более k.

Задача построения минимального доминирующего множества – одна из основных задач параметризованной сложности [ ]; она является W[2]-полной и, в связи с этим, едва ли окажется разрешимой при помощи алгоритмов с фиксированными параметрами. С другой стороны, на планарных графах она является разрешимой при помощи алгоритмов с фиксированными параметрами. С точки зрения аппроксимации эта задача эквивалентна задаче о минимальном покрытии множества при L-сведении. Существует алгоритм аппроксимации для нахождения минимального доминирующего множества с коэффициентом <math>1 + ln |V| \; </math>; эта задача не может быть аппроксимирована с коэффициентом <math>(1 - \epsilon ) \; ln |V|</math> для любого <math>\epsilon > 0 \; </math>, за исключением случая <math>NP \subset DTIME(n^{log \; log \; n})</math> [1].

'''Алгоритмы с умеренно экспоненциальным временем исполнения'''

Если <math>P \ne NP</math>, то алгоритмов с полиномиальным временем исполнения для построения минимального доминирующего множества не существует. Более того; в [7] было установлено, что за исключением случая <math>SNP \subseteq SUBEXP</math> (крайне маловероятного) не существует алгоритмов нахождения доминирующего множества даже с субэкспоненциальным временем исполнения.

Тривиальный алгоритм сложности <math>O(2^n (n+m)) \; </math>, который просто проверяет все <math>2^n \; </math> подмножеств вершин на вопрос, не являются ли они доминирующими, очевидным образом решает задачу нахождения доминирующего множества. В 2004 году были разработаны три более быстрых алгоритма. Фомин и коллеги [7] использовали результат из теории графов, установленный Б. Ридом, который показал, что каждый граф с n вершинам с минимальной степенью не менее трех имеет доминирующее множество размера не более <math>3n/8 \; </math>. Это позволило им разработать алгоритм, решающий задачу нахождения минимального доминирующего множества за время <math>O(2^{0.955n}) \; </math>. Алгоритм Рандерата и Ширмейера [11] с временем исполнения <math>O(2^{0.919n}) \; </math> использует любопытные идеи, включающие технику сопоставления, для ограничения пространства поиска. Наконец, Грандони [8] удалось разработать алгоритм нахождения минимального доминирующего множества за время <math>O(2^{0.850n}) \; </math>.

В работе Фомина, Грандони и Кратча [5] представлен простой и удобный для реализации рекурсивный алгоритм ветвления и редукции для решения этой задачи. Он исполняется значительно быстрее предыдущих алгоритмов. В его основе лежит анализ времени исполнения посредством подхода «измеряй и властвуй», представляющего собой метод анализа времени исполнения в наихудшем случае для простых алгоритмов ветвления и редукции, основанный на тщательном отборе меры экземпляра задачи.

Алгоритмы из теорем 1 и 2 представляют собой простые последовательности преобразований минимального доминирующего множества в [[минимальное покрытие множества]] (minimum set cover, MSC) в сочетании с новыми алгоритмами вычисления минимального покрытия множества, время исполнения которых является умеренно экспоненциальным.

Применяя меморизацию к алгоритму теоремы 3, можно улучшить время исполнения следующим образом.

Анализ времени исполнения (в наихудшем случае) простого алгоритма ветвления и редукции для нахождения минимального покрытия множества, приведенного в теореме 3, выполняется  

посредством тщательного выбора меры экземпляра задачи, которая позволяет получить значительно более низкую верхнюю границу, чем при использовании стандартной меры. Результатом тщательного анализа является набор рекуррентностей. Затем при помощи случайного локального поиска производится вычисление весов, используемых в определении меры, что дает наилучшую достижимую верхнюю границу для времени исполнения в наихудшем случае.

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

Существуют другие NP-полные задачи, связанные с доминированием, которые могут быть решены при помощи алгоритма с умеренно экспоненциальным временем исполнения, основанного на вышеприведенном алгоритме нахождения минимального покрытия множества: любой экземпляр исходной задачи преобразуется в экземпляр задачи минимального покрытия множества (желательно с <math>| \mathfrak{U} | = |S| \; </math>), после чего алгоритм из теорем 3 или 4 используется для решения ее, а следовательно, и исходной задачи. Примерами таких задач являются нахождение тотального доминирующего множества, k-доминирующего множества, k-центра и минимального доминирующего множества на расщепляемых графах.

Алгоритм «Измеряй и властвуй» и прочно связанный с ним алгоритм квази-выпуклого анализа Эпстайна [4] использовались для разработки и анализа множества алгоритмов с умеренно экспоненциальным временем исполнения для решения NP-полных задач: оптимизации, подсчета и перечисления. См., например, [2] и [6].