Доматическое число

В теории графов доматическое разбиение графа $G=(V,E)$ — это разбиение множества вершин $V$ на непересекающиеся множества $V_{1}$ , $V_{2}$ ,..., $V_{K}$ , такие, что каждое множество V_i является доминирующим множеством графа G. Рисунок справа показывает доматическое разбиение графа. На рисунке доминирующее множество $V_{1}$ состоит из жёлтых вершин, $V_{2}$ состоит из зелёных вершин, а $V_{3}$ состоит из синих вершин.

Доматическое число — это максимальный размер доматического разбиения, то есть максимальное число непересекающихся доминирующих множеств. Граф на рисунке имеет доматическое число 3. Легко видеть, что доматическое число не меньше 3, поскольку мы представили доматическое разбиение размером 3. Чтобы понять, что доматическое число не превосходит 3, сначала рассмотрим верхние границы.

Верхние границы[править | править код]

Пусть $\delta$ — минимальная степень графа $G$ . Доматическое число графа $G$ не превосходит $\delta +1$ . Чтобы это понять, рассмотрим вершину $v$ степени $\delta$ . Пусть $N$ состоит из вершины $v$ и её соседей. Мы знаем, что (1) каждое доминирующее множество $V_{i}$ должно содержать по меньшей мере одну вершину из $N$ (доминирование), и (2) каждая вершина из $N$ содержится максимум в одном доминирующем множестве $V_{i}$ (отсутствие пересечений). Таким образом, имеется максимум $|N|=\delta +1$ непересекающихся доминирующих множеств.

Граф на рисунке имеет минимальную степень $\delta =2$ , а потому его доминирующее число не превосходит 3. Тем самым мы показали, что доматическое число в точности равно 3. Рисунок показывает доматическое разбиение максимального размера.

Нижние границы[править | править код]

Если в графе нет изолированных вершин (то есть, $\delta$ ≥ 1), то доматическое число не меньше 2. Чтобы это понять, заметим, что (1) слабая 2-раскраска является доматическим разбиением, если нет изолированных вершин, и (2) любой граф имеет слабую 2-раскраску. Альтернативно, (1) наибольшее независимое множество является доминирующим множеством и (2) дополнение максимального независимого множества также является доминирующим множеством, если нет изолированных вершин.

На рисунке справа показана слабая 2-раскраска, которая является доматическим разбиением размера 2 — тёмные вершины являются доминирующим множеством, а светлые вершины — другим доминирующим множеством (светлые вершины образуют наибольшее независимое множество). См. статью «Слабая раскраска» для дополнительной информации.

Вычислительная сложность[править | править код]

Поиск доматического разбиения размера 1 тривиален — это $V_{1}=V$ . Найти доматического разбиения размера 2 (или выяснить, что такого разбиения не существует) просто — проверяем, что нет изолированных вершин, и если нет, находим слабую 2-раскраску.

Однако найти доматическое разбиение максимального размера трудно. В частности, следующая задача разрешимости, известная как задача о доматическом числе, является NP-полной: для заданного графа $G$ и целого числа $K$ определить, меньше или нет доматическое число графа $G$ значения $K$ . Таким образом, задача определения доматического числа заданного графа является NP-трудной задачей, так что задача нахождения доматического разбиения максимального размера также NP-трудна.

Существует аппроксимационный алгоритм полиномиального времени с логарифмической гарантией аппроксимации^[1], то есть можно найти доматическое разбиение, размер которого находится не далее чем на множитель $O(\log |V|)$ от оптимума.

Однако, при имеющих веские основания предположениях, не имеется аппроксимационного алгоритма полиномиального времени с подлогарифмическим аппроксимационным множителем^[1]. Конкретнее — аппроксимационный алгоритм полиномиального времени для доматического разбиения с аппроксимационным коэффициентом $(1-\epsilon )\ln |V|$ для константы $\epsilon >0$ подразумевает, что все задачи класса NP могут быть решены за слегка суперполиномиальное время $n^{O(\log \log n)}$ .

Сравнение с похожими понятиями[править | править код]

Доматическое разбиение: Разбиение вершин на непересекающиеся доминантные множества. Доматическое число — это максимальное число таких множеств.
Раскраска вершин: Разбиение вершин на непересекающиеся независимые множества. Хроматическое число является минимальным числом таких множеств.
Разбиение на клики: Разбиение вершин на непересекающиеся клики. Эквивалентно раскраске вершин дополнения графа.
Рёберная раскраска: Разбиение рёбер на непересекающиеся паросочетания. Рёберное хроматическое число — это минимальное число таких множеств.

Пусть G = (U ∪ V, E) — двудольный граф без изолированных вершин. Все рёбра имеют вид {u, v} ∈ E, где u ∈ U и v ∈ V. Тогда {U, V} является 2-раскраской вершин и доминантным разбиением размера 2. Множества U и V являются независимыми доминирующими множествами. Хроматическое число графа G в точности равно 2. Не существует 1-раскраски вершин. Доминантное число графа G не меньше 2. Может существовать большее доматическое разбиение. Например, полный двудольный граф K_n,n для любого n ≥ 2 имеет доматическое число n.

Примечания[править | править код]

↑ ¹ ² Feige, Halldórsson, Kortsarz, Srinivasan, 2002, с. 172–195.

Литература[править | править код]

Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5. A1.1.. A1.1: GT3
E. J. Cockayne, Stephen T. Hedetniemi. Optimal domination in graphs // IEEE Transactions on Circuits and Systems. — 1975. — Т. CAS-22, вып. 11. — С. 855–857. — doi:10.1109/TCS.1975.1083994.
Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan. Approximating the domatic number // SIAM Journal on Computing. — 2002. — Т. 32, вып. 1. — С. 172–195. — doi:10.1137/S0097539700380754.

[_826442add8183b71-1] ¹ ² Feige, Halldórsson, Kortsarz, Srinivasan, 2002, с. 172–195.

[1]