Меня интересует следующая проблема: учитывая множество X и подмножества X_1, ..., X_n из X, найдите раскраску элементов X с помощью k цветов, чтобы все элементы в каждом X_i были по-разному окрашены. Более конкретно, я смотрю на случай, когда все X_i имеют размер k. Известно ли это в литературе под каким-то именем? Я ищу характеристики окрашиваемых экземпляров и результаты по сложности (P против NP-hard). Например, для k = 2 окрашиваемые экземпляры соответствуют двудольным графам, и, таким образом, проблема может быть решена за полиномиальное время.
cc.complexity-theory
reference-request
np-hardness
hypergraphs
Фальк Хюффнер
источник
источник
Ответы:
Я полагаю, что это известно в литературе как проблема нахождения сильной k-раскраски для k-равномерного гиперграфа. Это должно быть хорошим местом для начала: [PDF] .
источник
Это также самое сложное, как окрашивание графа G = ( X , E ) , где E формируется путем превращения каждого X i в клику. Ваше ограничение, что все X i имеют размер k, означает, что вы можете покрыть каждое ребро G кликой на k вершинах.k G=(X,E) E Xi Xi k G k
источник
По крайней мере так же сложно, как раскраска произвольного графа G = ( V , E ) . Для каждого ребра e = { u , v } у вас есть подмножество X e = { u , v , x ( e , 3 ) , x ( e , 4 ) , … , x ( e , k ) } ; здесь каждый х ( еk G=(V,E) e={u,v} Xe={u,v,x(e,3),x(e,4),…,x(e,k)} является фиктивным элементом, которого нет ни в одном другом подмножестве. Если вы можете k- colour G , вы можете легко найти раскраску системы множеств (просто жадно раскрасить фиктивные элементы), и наоборот.x(e,j) k G
источник
Раскраска, в которой каждый гиперэксид является полихроматическим (или радугой ), также называется сильной окраской .
Заметим, что сильная раскраска гиперграфа является именно правильной раскраской графа Гайфмана гиперграфа. (Граф Гайфмана (или первичный граф, или 2-секционный ) гиперграфа формируется путем добавления ребер между любыми двумя вершинами, которые появляются вместе в некоторой гипергранице.)
Так что если вы ищете -colouring из г -равномерного гиперграфа H , то вы можете равноценно искать к -colouring из Gaifman графа H . Случай r = 2 соответствует раскраске графа, полиномиальному времени для k = 2 и NP-полному для k ≥ 3 . Очевидно, что r < 2 тривиально, k < r не приводит к решениям, а все остальные случаи являются NP-полными.k r H k H r=2 k=2 k≥3 r<2 k<r
Полезным справочным материалом, который имеет большинство приведенных выше определений, является Виталий Иванович Волошин, « Раскрашивание смешанных гиперграфов: теория, алгоритмы и приложения» , «Монография 17 полей» , AMS, 2002, ISBN 0-8218-2812-6. Эта книга охватывает более общий случай слабых раскрасок, с особым акцентом на объединение двух типов цветных ребер: ребра , которые имеют по крайней мере две вершины с общим цветом, и D- ребра, которые имеют по крайней мере две вершины разных цвета.C D
источник