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

Домашняя перегородка

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

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

Верхние границы

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

Граф на рисунке имеет минимальную степень , и, следовательно, его домашнее число не превосходит 3. Следовательно, мы показали, что его домашнее число равно в точности 3; на рисунке показан домашний раздел максимального размера. ${\displaystyle \delta =2}$

Нижние границы

Слабая 2-раскраска

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

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

Вычислительная сложность

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

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

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

Однако при правдоподобных предположениях теории сложности не существует алгоритма аппроксимации с полиномиальным временем и сублогарифмическим коэффициентом аппроксимации. ^[1] Более конкретно, алгоритм аппроксимации с полиномиальным временем для домашнего разделения с коэффициентом аппроксимации для константы будет означать, что все проблемы в NP могут быть решены за слегка суперполиномиальное время . ${\displaystyle (1-\epsilon )\ln |V|}$ ${\displaystyle \epsilon >0}$ ${\displaystyle 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 .

Примечания

1. Файги, Уриэль ; Халльдорссон, Магнус М.; Корцарз, Гай; Шринивасан, Аравинд (март 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.