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

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

Задача построения минимального доминирующего множества – одна из основных задач параметризованной сложности [3]; она является 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. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального доминирующего множества за время <math>O(2^{0:610n}) \; </math> с использованием полиномиального объема памяти.

Дано: конечное множество <math>\mathfrak{U} \; </math> и набор <math>S \; </math> подмножеств <math>S_1, S_2,... S_t \; </math> множества <math>\mathfrak{U} \; </math>.

Требуется: найти минимальное покрытие множества <math>S' \; </math>, где <math>S' \subseteq S \; </math> – покрытие множества <math>(\mathfrak{U}, S) \; </math>, если <math> \bigcup_{S_i \in S'} S_i = \mathfrak{U} \; </math>

'''Теорема 3. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального покрытия множества за время <math>O(2^{0.305(|U| + |S|)}) \; </math> с использованием полиномиального объема памяти.'''

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

'''Теорема 4. Существует алгоритм, способный решить задачу нахождения минимального покрытия множества за время <math>O(2^{0.299(|S| + |U|)}) \; </math> с использованием экспоненциального объема памяти.'''

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

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

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

'''Теорема 5. Существует алгоритм ветвления и редукции в наихудшем случае, способный решить задачу нахождения минимального доминирующего множества (см. теорему 1) за время <math>\Omega (2^{n/3}) \; </math>.'''

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

Простые алгоритмы ветвления и редукции в наихудшем случае, подобные алгоритмам нахождения минимального доминирующего множества или минимального покрытия множества, также пока неизвестны. В случае алгоритма нахождения минимального доминирующего множества с использованием полиномиального объема памяти разрыв между верхней границей <math>O(2^{0.610n}) \; </math> и нижней границей <math>\Omega (2^{n/3}) \; </math> слишком велик. Подобная же ситуация наблюдается и для других алгоритмов ветвления и редукции. Следовательно, существует значительная потребность в новых и более мощных инструментах анализа алгоритмов ветвления и редукции в наихудшем случае.

* ''[[Вершинное покрытие и деревья поиска]]