Алгоритмические аспекты доминирования в графах

 

В данной статье с алгоритмической точки зрения исследуется одна из оптимизационных задач теории графов — задача о доминировании, которая является естественной моделью для многих задач размещения, изучаемых в исследовании операций и возникающих в многочисленных приложениях. Приведено обоснование её значимости как широко применимой задачи, для которой доказано свойство NP-полноты. Автором разработана и описана программа, реализованная на основе алгоритмов дискретной оптимизации и жадного алгоритма, позволяющая различными методами найти решения задачи о доминировании для последующего их сравнения.

Ключевые слова: доминирование, доминирующее множество, число доминирования, задачи размещения, методы дискретной оптимизации, NP-полнота, динамическое программирование, прямо-двойственный алгоритм, жадный алгоритм, остовное дерево, задача о наименьшем покрытии.

 

Задача о доминировании имеет различные формулировки. В классической теоретико‑графовой постановке она звучит так: в заданном графе G = (V, E) найти наименьшее по мощности подмножество вершин DV такое, что каждая вершина из V \ D является смежной по меньшей мере с одной вершиной из D. При этом найденное множество D называется наименьшим доминирующим множеством, а его мощность — числом доминирования γ(G) графа G.

В распознавательном варианте классическая задача о доминировании формулируется следующим образом.

ЗАДАЧА О ДОМИНИРОВАНИИ

УСЛОВИЕ: Связный граф G = (V, E) и натуральное число k |V|.

ВОПРОС: Существует ли подмножество DV такое, что |D| k и для любой вершины x V верно N [x]  D?

Доказательство NP‑полноты данной задачи основано на полиномиальном сведении к ней задачи о вершинном покрытии [1].

ЗАДАЧА О ВЕРШИННОМ ПОКРЫТИИ

УСЛОВИЕ: Связный граф G = (V, E) и натуральное число k |V|.

ВОПРОС: Существует ли подмножество CV такое, что |C| k и для каждого ребра xyE верно xC или y C?

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

Задача о доминировании изучалась с начала 1970-х годов. Стимулом для этого послужили классические задачи о покрытии шахматных досок минимальным количеством шахматных фигур [3]. Многие теоремы для задачи о доминировании были сформулированы и доказаны, начиная с 1970‑х годов, однако первый алгоритмический результат был получен [4] лишь в 1975 году. Авторы работы [4] предложили алгоритм, линейный по времени для задачи о доминировании на деревьях, использующий метод маркировки. Примерно в то же самое время Гэри и Джонсон [1] доказали, что задача о доминировании является NP‑полной для графов общего вида. С тех пор и до настоящего времени предлагаются многие алгоритмические результаты для всевозможных вариантов задачи о доминировании для разных классов графов. В связи с широким применением задачи о доминировании в современных областях науки и техники, по-прежнему остаются актуальными исследования, направленные на разработку алгоритмов её решения.

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

Как было сказано выше, в работе [1] доказано, что классическая задача о доминировании является NP‑полной. Она остаетсяNP‑полной для узкихклассов графов, в том числе плоских, двудольных и хордальных графов. Известно много других NP‑полных результатов для различных вариантов задачи о доминировании [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] и [4, 20, 21]. Однако эта задача может быть решеназа полиномиальное время, например, для деревьев, графов перестановок и интервальныхграфов.

Алгоритм полного перебора анализирует все 2N различных подмножеств множества из N вершин графа на предмет того, является ли очередное подмножество доминирующим множеством графа, устанавливая тривиальную верхнюю оценку вычислительной сложности задачи о доминировании в худшем случае. С начала 70-х годов прошлого века и до настоящего времени активно ведется поиск алгоритмов, работающих быстрее полного перебора [22]. Среди них мы подробно рассматриваем вышеуказанные методы дискретной оптимизации, а также жадный алгоритм.

Динамическое программирование — мощный метод решения многих задач дискретной оптимизации [23, 24, 25]. Основная идея динамического программирования для задачи о доминировании — просмотр вершин дерева «сверху‑вниз» вместо просмотра «снизу‑вверх» как в алгоритме маркировки.

Выделим в графе G некоторую вершину u. Тогда минимальное доминирующее множество D для G либо содержит вершину u, либо не содержит. Значит, можно рассматривать следующие две задачи о доминировании:

γ1(G, u) = min {|D|: D — доминирующее множество для G и uD};

γ0(G, u) = min {|D|: D — доминирующее множество для G и uD}.

Лемма 2.1Для любого графаG с выделенной вершиной u верно равенствоγ(G) = min{γ1(G, u), γ0(G, u)}.

Предположим, что H — другой граф с выделенной вершиной v. Пусть граф I с выделенной вершиной u получается объединением G и H с помощью нового ребра uv (рисунок 1).

Рис. 1. Объединение деревьев G и H с помощью ребра uv

 

Суть метода динамического программирования для задачи о доминировании состоит в поиске значений γ1(I, u) и γ0(I, u) для графа I на основе чисел γ1(G, u), γ0(G, u), γ1(H, v), γ0(H, v), найденных для графовG и H.

Рассмотрим доминирующее множество D для графа I с выделенной вершиной u. Тогда D = D'D«, где D' — доминирующее множество для G с vD', и D'' — подмножество из V(H), доминирующее над V(H) {v}. Возможны два случая. Если vD'', то D'' — доминирующее множество для H. Если v D'', то D'' — доминирующее множество для H — v. В последнем случае, требуется найти

γ00(G, u) = min {|D|: D — доминирующее множество для G — u}.

Заметим, что γ00(G, u) ≤ γ0(G, u), так как доминирующее множество D для G с uD также является доминирующим множеством для G — u.

Теорема 2.2 Пусть G и H — графы с выделенными вершинами u и v соответственно. ПустьI — граф с выделенной вершиной u, который получается объединениемG иH с помощью нового ребра uv. Тогда справедливы утверждения.

(1)               γ1(I, u) = γ1(G, u) + min {γ1(H,v), γ00(H,v)}.

(2)               γ0(I, u) = min {γ0(G, u) + γ0(H,v), γ00(G, u) + γ1(H,v)}.

(3)               γ00(I, u) = γ00(G, u) + γ(H) = γ00(G, u) + min {γ1(H,v), γ0(H,v)}.

Из леммы 2.1 и теоремы 2.2 вытекает следующий алгоритм динамического программирования для задачи о доминировании на деревьях.

АлгоритмDomTreeD. Нахождение числа доминирования дерева.

Вход: дерево T с порядком вершин TO (v1, v2,..., vn).

Выход: число доминирования γ(T) для T.

Метод

for i = 1 to n do

γ1(vi) ← 1;

γ0(vi) ← ∞;

γ00(v) ← 0;

end do;

for i = 1 to n  1 do

Пусть vj является родителем для vi;

γ1(vi ← γ1(vj) + min{γ1(vi), γ00(vi)};

γ0(vj) ← min{γ0(vj) + γ0(vi), γ00(vj) + γ1(vi)};

γ00(vj) ← γ00(vj) + min{γ1(vi), γ0(vi)};

end do;

γ(T) ← min{γ1(vn), γ0(vn)}.

Преимущество метода динамического программирования заключается в том, что он является применимым к задачам, решения которых не обладают свойством локальности. Например, к задаче о независимом доминировании [26]. Кроме того, данный метод динамического программирования можно использовать для решения вершинно‑реберно‑взвешенных случаев доминирования.

Самым изящным методом, используемым в доминировании, является прямо‑двойственный подход. В этом методе помимо исходной задачи о доминировании рассматривается следующая двойная задача.

В графе G = (V, E) под 2‑устойчивым множеством понимается подмножествоSV, в котором для любых двух различных вершин u и v расстояние d(u, v) > 2. Число 2‑устойчивости2(G) графа G — это наибольшая мощность его 2‑устойчивого множества.

Нетрудно убедиться, что для любого графа G всегда выполняется неравенство слабой двойственности:

2(G) γ(G).

Это неравенство может быть строгим. Например, для графа Cn

2(Cn) = [n / 3], γ(Cn) = [n / 3].

Разработаем алгоритм, который выдает для дерева T минимальное доминирующее множество D*, 2‑устойчивое множество S* и |D*|  |S*|. Тогда, исходя из неравенства слабой двойственности, имеем

|S*| 2 (T) γ(T)  |D*|  |S*|,

и все неравенства становятся равенствами. Следовательно, D* — это наименьшее доминирующее множество, S* — это наибольшее 2‑устойчивое множество, а 2(T) = γ(T).

Алгоритм начинает работу с листа v, смежного с вершиной u. Он использует ту же идею, что в алгоритме маркировки: u предпочтительнее v, так как N [v] N [u]. Вместо v в D* помещается u. Также в S* помещается v.

Алгоритм DomTreePD. Найти наименьшее доминирующее множество и наибольшее 2‑устойчивое множество дерева.

Вход: дерево T с порядком вершин TO (v1, v2,..., vn).

Выход: наименьшее доминирующее множество D* и наибольшее 2‑устойчивое множество S* для T.

Метод

D*  ;

S*  ;

for i = 1 to n do

Пусть vj является родителем для vi; (считать vj = vn при vi = vn)

if N[vi]  D* =  then

D*  D*  {vj}; S*  S* ∪ {vi};

end do.

Выбранный нами жадный алгоритм основывается на возможности сведения задачи о доминировании к задаче о наименьшем покрытии (ЗНП). Задача отыскания наименьшего доминирующего множества вершин неориентированного графа G соответствует ЗНП с матрицей P, в качестве которой выступает матрица смежности графа G с единичными элементами на главной диагонали. Приведем жадный алгоритм нахождения доминирующего множества, построенный на основе алгоритма решения ЗНП с единичными весами градиентным методом.

Алгоритм DomSet. Найти доминирующее множество графа G общего вида.

Вход: матрица смежности P размером n×n графа G общего вида.

Выход: доминирующее множество D** заданного графа.

Метод

D** ;

1.                На главной диагонали матрицы смежности P проставить единичные элементы.
2.                Выделить столбец матрицы смежности, содержащий наибольшее число единиц. Если таких столбцов несколько, то выбрать любой из них. В матрице P вычеркнуть (считать покрытыми) все строки, содержащие единицу в выделенном столбце. В множество D* добавить номер выбранного столбца в качестве номера вершины доминирующего множества.
3.                На k-м шаге выполнить те же действия (из пункта 2) над матрицей, полученной на предыдущем шаге. Процесс завершить, если все строки матрицы оказались вычеркнутыми.

В процессе исследования автором статьи разработана программа SOD (SearchOfDomination), которая находит различные решения для задачи о доминировании с помощью как методов дискретной оптимизации, так и жадного алгоритма. В программе для исходного графа общего вида выполняется построение остовного дерева, для которого с помощью методов динамического программирования и прямо-двойственного подхода определяются доминирующее множество и число доминирования. То есть мы получаем точное решение задачи о доминировании для остовного дерева, которое является приближенным для исходного графа. Затем для исходного графа с помощью жадного алгоритма находится еще одно решение и сравнивается с приближенным, полученным путем применения алгоритмов дискретной оптимизации к остовному дереву графа.

Функциональное назначение процедур программы SOD представлено в таблице 1.

 

Таблица 1

Функциональное назначение процедур

Процедура	Назначение процедуры
minimum	Определение меньшего из двух чисел, предоставленных как параметры функции.
reading_from_file	Чтение из файла информации о вершинах (их номера и номера вершин в их окрестности) и заполнение начальными значениями чисел γ0(vi), γ1(vi), γ00(vi) для каждой вершины vi. В дальнейшем эти числа используются для вычисления числа доминирования графа.
find_father	Поиск вершины‑родителя для заданной вершины по её номеру. В качестве выходных данных возвращает номер родительской вершины и её порядковый номер в «порядке дерева (TO)».
printing_to_file	Распечатка вектора v в выходной файл в виде номеров вершин и номеров вершин их окрестностей.
printing_to_file_numb	Распечатка вектора v в виде номеров вершин vi и значений их чисел γ0(vi), γ1(vi), γ00(vi).
delete_numb_from_vector	Удаление вершины по её номеру из окрестностей всех вершин вектора.
tree_ordering	Построение порядка дерева (TO, Tree Ordering).
dynamic_programming_algorithm	Поиск числа доминирования дерева с помощью динамического программирования.
primal_dual_algorithm	Поиск наименьшего доминирующего и наибольшего 2‑устойчивого множеств дерева с помощью прямо-двойственного подхода.
greed_algorithm	Поиск доминирующего множества графа общего вида с помощью жадного алгоритма
main	Главная функция, тело программы, в котором реализуются все вышеуказанные действия и алгоритмы.

 

Для эксплуатации программы необходимо иметь персональный компьютер типа IBMPCPentiumIV с операционной системой WindowsXP/Vista и оперативной памятью от 512 Мб.

Для создания программы использована среда разработки MicrosoftVisualStudioCommunity 2015, язык программирования C++. Программа работает с вектором (класс из стандартной библиотеки C++) структур, состоящих из номера вершины, её порядкового номера (для дальнейшего построения «порядка дерева»), чисел, которые далее используются для нахождения числа доминирования и вложенного вектора, используемого для хранения информации об окрестности вершины (её потомках в дереве). Данные структуры инициализируются для работы с заданным деревом в программном виде.

Входные данные задаются в виде текстового файла в определенном формате, в котором указываются количество вершин и информация о каждой вершине в виде:xiy1 … yn, где xi — номер вершины, y1 … yn — номера вершин, смежных вершине xi (то есть окрестность вершины xi). Выходные данные имеют следующую структуру:

1)                 структура графа в виде массива окрестностей каждой вершины

2)                 построенный порядок (упорядочивание) дерева;

3)                 число доминирования дерева, полученное динамическим программированием;

4)                 доминирующее множество дерева, найденное через построение остовного дерева графа и применение к нему прямо-двойственного подхода;

5)                 доминирующее множество дерева, найденное через жадный алгоритм;

6)                 наибольшее 2-устойчивое множество дерева, найденное через построение остовного дерева графа и применение к нему прямо-двойственного подхода.

Разработанная программа SOD была проверена на большом количестве графов разных классов. Приведем пример одного из них. Рассмотрим граф общего вида, включающий в себя 13 вершин и 19 рёбер:

Для данного графа программа строит остовное дерево и находит решение задачи о доминировании, применяя динамическое программирование, прямо-двойственный подход и жадный алгоритм. Выходные данные программы и замеры времени представлены ниже.

 

Как мы видим, и прямо-двойственный, и жадный алгоритмы нашли решение задачи о доминировании. Но при этом решение прямо-двойственного алгоритма избыточно (на 1 вершину больше, чем у жадного), а решение жадного алгоритма более точно. Кроме того, жадный алгоритм сработал в 8 раз быстрее, чем прямо-двойственный алгоритм, и в 6 раз быстрее, чем динамическое программирование, которое при этом ищет только число доминирования, но не доминирующее множество. Также при данных подсчетах не было учтено дополнительное время на построения остовного дерева и порядка данного дерева, которые необходимы для применения динамического программирования и прямо-двойственного подхода. Отсюда разница по времени выполнения между жадным алгоритмом и вышеуказанными методами дискретной оптимизации становится еще более очевидной.

Рис. 2. Результат выполнения программы для графа с 13 вершинами и 19 ребрами

 

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

Разработанная программа может быть использована в многочисленных приложениях задачи о доминировании и прикладных задачах, сводимых к ней.

 

Литература:

 

1          M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

2          T. W. Haynes, S. T. Hedetniemi and P. J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York, 1997.

3          C. F. De Jaenisch. Applications de l’Analuse mathematique an Jen des Echecs.Petrograd, 1862.

4          E. J. Cockayne, S. E. Goodman and S. T. Hedetniemi. A linear algorithm for the domination number of a tree. Inform. Process. Lett., 4:41–44, 1975.

5          D. W. Bange, A. E. Barkauskas and P. J. Slater. Efficient dominating sets in graphs. In R. D. Ringeisen and F. S. Roberts, editors, Applications of Discrete Mathematics, pages 189–199. SIAM, Philadelphia, PA, 1988.

6          A. A. Bertossi. Dominating sets for split and bipartite graphs. Inform. Process. Lett., 19:37–40, 1984.

7          K. S. Booth and J. H. Johnson. Dominating sets in chordal graphs. SIAM J. Comput., 11:191–199, 1982.

8          D. G. Corneil and J. M. Keil. A dynamic programming approach to the dominating set problem on k-trees. SIAM J. Algebraic Discrete Methods, 8:535–543, 1987.

9          D. G. Corneil and Y. Perl. Clustering and domination in perfect graphs. Discrete Appl. Math., 9:27–39, 1984.

10      P. Damaschke, H. Muller and D. Kratsch. Domination in convex and chordal bipartite graphs. Inform. Process. Lett., 36:231–236, 1990.

11      M. Farber. Independent domination in chordal graphs. Oper. Res. Lett., 1:134–138, 1982.

12      M. R. Fellows and M. N. Hoover. Perfect domination. Australas. J. Combin., 3:141–150, 1991.

13      S. M. Hedetniemi, S. T. Hedetniemi and D. P. Jacobs. Private domination: theory and algorithms. Congr. Numer., 79:147–157, 1990.

14      S. F. Hwang and G. J. Chang. The k-neighbor domination problem in block graphs. European J. Oper. Res., 52:373–377, 1991.

15      H. Muller and A. Brandstadt. The NP-completeness of STEINER TREE and DOMINATING SET for chordal bipartite graphs. Theoret. Comput. Sci., 53:257–265, 1987.

16      C. Yen and R. C. T. Lee. The weighted perfect domination problem. Inform. Process. Lett., 35(6):295–299, 1990.

17      C. Yen and R. C. T. Lee. The weighted perfect domination problem. Inform. Process. Lett., 35(6):295–299, 1990.

18      Коробицын, Д. В. О сложности определения числа доминирования в моногенных классах графов / Д. В. Коробицын // Дискретная математика. — 1990. — № 2 (3) — С. 90‑97.

19      Тараканов, В. Е. Комбинаторные задачи и (0, 1)-матрицы / В. Е. Тараканов // Москва «Наука». — Главная редакция физико-математической литературы. — 1985. — С. 170–173.

20      T. S. Jayaram, G. Sri Karishna and C. Pandu Rangan. A unified approach to solving domination problems on block graphs. Report TR-TCS-90–09, Dept. of Computer Science and Eng., Indian Inst. of Technology, 1990.

21      D. S. Johnson. The NP-completeness column: an ongoing guide. J. Algorithms, 6:291–305,434–451, 1985.

22      S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial K-trees. Discrete Appl. Math., 23:11–24, 1989.

23      R. E. Bellman and S. E. Dreyfus. Applied Dynamic Programming. Princeton University Press, 1962.

24      C. F. De Jaenisch. Applications de l’Analuse mathematique an Jen des Echecs.Petrograd, 1862.

25      G. L. Nemhauser. Introduction to Dynamic Programming. John Wiley & Sons, 1966.

26      T. A. Beyer, A. Proskurowski, S. T. Hedetniemi and S. Mitchell. Independent domination in trees. Congr. Numer, 19:321–328, 1977.