«Все-разные раскраски гиперграфа» - известная проблема?

18

Меня интересует следующая проблема: учитывая множество X и подмножества X_1, ..., X_n из X, найдите раскраску элементов X с помощью k цветов, чтобы все элементы в каждом X_i были по-разному окрашены. Более конкретно, я смотрю на случай, когда все X_i имеют размер k. Известно ли это в литературе под каким-то именем? Я ищу характеристики окрашиваемых экземпляров и результаты по сложности (P против NP-hard). Например, для k = 2 окрашиваемые экземпляры соответствуют двудольным графам, и, таким образом, проблема может быть решена за полиномиальное время.

Фальк Хюффнер
источник
Если гиперграф имеет ограниченную степень D, то максимальное число используемых цветов - тэта (D / log k): см. Arxiv.org/abs/1009.5893 или arxiv.org/abs/1009.6144
daveagp
Если вы заинтересованы в учебнике с этими типами раскрасок, посмотрите на amazon.com/Introduction-Hypergraph-Theory-Vitaly-Voloshin/dp/… Если вы хотите узнать больше о применениях раскраски гиперграфа, посмотрите на бумага research.microsoft.com/en-us/um/people/moscitho/Publications/...

Ответы:

14

Я полагаю, что это известно в литературе как проблема нахождения сильной k-раскраски для k-равномерного гиперграфа. Это должно быть хорошим местом для начала: [PDF] .

Джеймс Кинг
источник
10

Это также самое сложное, как окрашивание графа G = ( X , E ) , где E формируется путем превращения каждого X i в клику. Ваше ограничение, что все X i имеют размер k, означает, что вы можете покрыть каждое ребро G кликой на k вершинах.kG=(X,E)EXiXikGk

Серж Гасперс
источник
1
В самом деле. Это похоже на трансформацию Covering By Cliques в Garey / Johnson. NP-полная для фиксированного , но имеет алгоритм полиномиального времени для k 2 (как упоминает Фальк). k3k2
Даниэль Апон
2
Предложенная здесь конструкция в точности является графом Гайфмана. G
Андрас Саламон
Это верно. действительно является графом Гайфмана. G
Серж Гасперс
8

По крайней мере так же сложно, как раскраска произвольного графа G = ( V , E ) . Для каждого ребра e = { u , v } у вас есть подмножество X e = { u , v , x ( e , 3 ) , x ( e , 4 ) , , x ( e , k ) } ; здесь каждый х ( еkG=(V,E)e={u,v}Xe={u,v,x(e,3),x(e,4),,x(e,k)} является фиктивным элементом, которого нет ни в одном другом подмножестве. Если вы можете k- colour G , вы можете легко найти раскраску системы множеств (просто жадно раскрасить фиктивные элементы), и наоборот.x(e,j)kG

Юкка Суомела
источник
8

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

Заметим, что сильная раскраска гиперграфа является именно правильной раскраской графа Гайфмана гиперграфа. (Граф Гайфмана (или первичный граф, или 2-секционный ) гиперграфа формируется путем добавления ребер между любыми двумя вершинами, которые появляются вместе в некоторой гипергранице.)

Так что если вы ищете -colouring из г -равномерного гиперграфа H , то вы можете равноценно искать к -colouring из Gaifman графа H . Случай r = 2 соответствует раскраске графа, полиномиальному времени для k = 2 и NP-полному для k 3 . Очевидно, что r < 2 тривиально, k < r не приводит к решениям, а все остальные случаи являются NP-полными.krHkHr=2k=2k3r<2k<r

Полезным справочным материалом, который имеет большинство приведенных выше определений, является Виталий Иванович Волошин, « Раскрашивание смешанных гиперграфов: теория, алгоритмы и приложения» , «Монография 17 полей» , AMS, 2002, ISBN 0-8218-2812-6. Эта книга охватывает более общий случай слабых раскрасок, с особым акцентом на объединение двух типов цветных ребер: ребра , которые имеют по крайней мере две вершины с общим цветом, и D- ребра, которые имеют по крайней мере две вершины разных цвета.CD

Андраш Саламон
источник
Что бы вы посоветовали в качестве цитаты для NP-сложности проблемы? Выше книга?
Домоторп
@domotorp нет, книга посвящена слабой окраске. Смотрите ответ Юкки.
Андрас Саламон