"Coloración hipergráfica completamente diferente" - ¿problema conocido?

18

Estoy interesado en el siguiente problema: dado un conjunto X y los subconjuntos X_1, ..., X_n de X, encuentre una coloración de los elementos de X con k colores de manera que los elementos en cada X_i sean todos de colores diferentes. Más específicamente, estoy mirando el caso donde todos los X_i son de tamaño k. ¿Es esto conocido en la literatura con algún nombre? Estoy buscando caracterizaciones de instancias coloreables y resultados de complejidad (P vs. NP-hard). Por ejemplo, para k = 2, las instancias colorables corresponden a gráficos bipartitos y, por lo tanto, el problema puede resolverse en tiempo polinómico.

Falk Hüffner
fuente
Si la hipergrafía tiene un límite D, el número máximo de colores que se pueden usar es Theta (D / log k): consulte arxiv.org/abs/1009.5893 o arxiv.org/abs/1009.6144
daveagp
Si está interesado en un libro de texto con este tipo de coloración, visite amazon.com/Introduction-Hypergraph-Theory-Vitaly-Voloshin/dp/... Si está interesado en obtener más información sobre las aplicaciones de coloración de hipergrafía, eche un vistazo a paper research.microsoft.com/en-us/um/people/moscitho/Publications/…

Respuestas:

14

Creo que esto se conoce en la literatura como el problema de encontrar una coloración k fuerte para una hipergrafía k-uniforme. Este debería ser un buen lugar para comenzar: [PDF] .

James King
fuente
10

También es, como máximo, tan difícil como colorear una gráfica , donde se forma al convertir cada en una camarilla. Su restricción de que todas las son de tamaño significa que puede cubrir cada borde de con una camarilla en vértices.G = ( X , E ) E X i X i k G kkG=(X,E)EXiXikGk

Serge Gaspers
fuente
1
En efecto. Esto parece una transformación de Covering By Cliques en Garey / Johnson. NP-complete para fijo , pero tiene un algoritmo de tiempo polinómico para (como menciona Falk). k 2k3k2
Daniel Apon
2
La construcción de sugerida aquí es precisamente el gráfico de Gaifman. G
András Salamon
G
8

kG=(V,E)e={u,v}Xe={u,v,x(e,3),x(e,4),,x(e,k)}x(e,j)kG

Jukka Suomela
fuente
8

Un colorante en el que cada hiperedge es policromático (o arcoíris ) también se conoce como un colorante fuerte .

Tenga en cuenta que una fuerte coloración de una hipergrafía es precisamente una coloración adecuada del gráfico de Gaifman de la hipergrafía. (El gráfico de Gaifman (o gráfico primario o 2 secciones ) de una hipergrafía se forma agregando bordes entre dos vértices que aparecen juntos en alguna hiperedificación).

krHkHr=2k=2k3r<2k<r

CD

András Salamon
fuente
¿Qué recomendaría como cita para la dureza NP del problema? El libro de arriba?
domotorp
@domotorp no, el libro se centra en la coloración débil. Ver la respuesta de Jukka.
András Salamon