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

Ключевые слова и синонимы

Связное доминирующее множество

Постановка задачи

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

Определение 1. Пусть задан простой неориентированный граф G = (V, E). Подмножество вершин [math]\displaystyle{ D \subseteq V }[/math] называется доминирующим множеством, если каждая вершина [math]\displaystyle{ u \in V - D \; }[/math] имеет соседа в D. Задача построения минимального доминирующего множества (minimum dominating set, MDS) заключается в поиске минимального доминирующего множества графа G, т.е. доминирующего множества G с минимальной мощностью.

Задача 1 (минимальное доминирующее множество, MDS)

Дано: простой неориентированный граф G = (V, E).

Требуется: найти минимальное доминирующее множество D графа G.

Представляют интерес различные модификации задачи построения доминирующего множества; некоторые из них были получены посредством накладывания дополнительных ограничений на доминирующее множество – к примеру, оно может быть независимым или связным. В теории графов проблеме доминирования и множеству ее модификаций посвящен обширный список работ (см., например, [9]). В контексте графовых алгоритмов задача построения минимального доминирующего множества и некоторых его модификаций (таких как независимое доминирующее множество или связное доминирующее множество) рассматривается как типовая для решения NP-полных задач с использованием различных алгоритмических подходов.

Известные результаты

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

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

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

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

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

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

Основные результаты

Теорема 1. Существует алгоритм ветвления и редукции, способный решить задачу нахождения минимального доминирующего множества за время [math]\displaystyle{ O(2^{0:610n}) \; }[/math] с использованием полиномиального объема памяти.

Теорема 2. Существует алгоритм, способный решить задачу нахождения минимального доминирующего множества за время [math]\displaystyle{ O(2^{0:598n}) \; }[/math] с использованием экспоненциального объема памяти.

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

Задача 2 (минимальное покрытие множества, MSC)

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

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

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

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

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

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

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

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

Применение

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

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

Открытые вопросы

Некоторые задачи, имеющие отношение к работе Фомина, Грандони и Кратча, остаются нерешенными. Хотя для различных классов графов разработаны алгоритмы нахождения минимального доминирующего множества, более быстрые по сравнению с алгоритмами для графов общего вида (о них идет речь в теоремах 1 и 2), для двудольных графов таких алгоритмов пока не найдено.

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

См. также

• Связное доминирующее множество
• Редукция данных для доминирования в графах
• Вершинное покрытие дерева поиска

Литература

1. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccalema, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)

2. Byskov, J.M.: Exact algorithms for graph colouring and exact satisfiability. Ph.D. thesis, University of Aarhus, Denmark (2004)

3. Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, New York (1999)

4. Eppstein, D.: Quasiconvex analysis of backtracking algorithms. I n: Proceed i ng s of SODA 2004, pp. 781 -790

5. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: Domination - A case study. In: Proceedings of ICALP 2005. LNCS, vol. 3380, pp. 192-203. Springer, Berlin (2005)

6. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and Conquer: A simple O(20.288n) Independent Set Algorithm. In: Proceedings of SODA 2006, pp. 18-25

7. Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings of WG 2004. LNCS, vol. 3353, pp. 245-256. Springer, Berlin (2004)

8. Grandoni, F.: Exact Algorithms for Hard Graph Problems. Ph. D. thesis, Universita di Roma "Tor Vergata", Roma, Italy (2004)

9. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker, New York (1998)

10. Kratsch, D.: Algorithms. In: Haynes, T., Hedetniemi, S., Slater, P. (eds.) Domination in Graphs: Advanced Topics, pp. 191-231. Marcel Dekker, New York (1998)

11. Randerath, B., Schiermeyer, I.: Exact algorithms for MINIMUM DOMINATING SET. Technical Report, zaik-469, Zentrum fur Angewandte Informatik Koln (2004)

12. Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization - Eureka, You Shrink.LNCS, vol. 2570, pp. 185-207. Springer, Berlin (2003)