Домашний номер

В теории графов — домашнее разбиение графа . $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 .

Примечания

^ Jump up to: ^а ^б Файги, Уриэль ; Халлдорссон, Магнус М.; Корцарз, Гай; Шринивасан, Аравинд (март 2002 г.), «Приближение домашнего числа», SIAM Journal on Computing , 32 (1): 172–195, doi : 10.1137/S0097539700380754 , MR 1954859

Ссылки

Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . . A1.1: GT3, с. 190.
Кокейн, Э.Дж.; Хедетниеми, Стивен Т. (1975), «Оптимальное доминирование в графах», Транзакции IEEE в схемах и системах , CAS-22 (11): 855–857, doi : 10.1109/TCS.1975.1083994 , MR 0384608 .

[feige-2002-1] Jump up to: ^а ^б Файги, Уриэль ; Халлдорссон, Магнус М.; Корцарз, Гай; Шринивасан, Аравинд (март 2002 г.), «Приближение домашнего числа», SIAM Journal on Computing , 32 (1): 172–195, doi : 10.1137/S0097539700380754 , MR 1954859

[1]