Algoritmo eficiente para coloraciones de borde casi óptimas de hipergrafías

12

Los problemas de coloración de gráficos ya son bastante difíciles para la mayoría de las personas . Aun así, voy a tener que ser difícil y preguntar un problema sobre el color de la hipergrafía.

Pregunta.

¿Qué algoritmos eficientes existen para encontrar una coloración de borde aproximadamente óptima para las hipergrafías k uniformes?

Detalles ---

  • Una hipergrafía k uniforme es aquella en la que cada arista contiene precisamente k vértices; El caso habitual de un gráfico simple es k = 2. Más precisamente, estoy interesado en las hipergrafías etiquetadas con uniforme k, en las que dos bordes pueden tener el mismo conjunto de vértices; pero me conformaré con algo en las hipergrafías k-regulares con bordes que se cruzan en no más de k-1 vértices.

  • Una coloración de borde de las hipergrafías es aquella en la que los bordes del mismo color no se cruzan, como en el caso de los gráficos. El índice cromático χ '(H) es el número mínimo de colores requeridos, como de costumbre.

  • Me gustaría obtener resultados en algoritmos de tiempo polinomiales deterministas o aleatorios.

  • Estoy buscando el factor de aproximación / brecha aditiva más conocido entre lo que se puede encontrar eficientemente y el índice cromático real χ '(H) --- o, para el caso, el mejor resultado eficientemente alcanzable en términos de parámetros como el grado máximo de vértice Δ (H), el tamaño de la hipergrafía, etc.

Editar: provocado por las observaciones de Suresh sobre los dobles de hipergrafía a continuación, debo señalar que este problema es equivalente al problema de encontrar una coloración de vértice fuerte de una hipergrafía k-regular : es decir, donde cada vértice pertenece a k bordes distintos [pero los bordes ahora puede contener diferentes números de vértices], y queremos un color de vértice tal que dos vértices adyacentes tengan diferentes colores. Esta reformulación tampoco parece tener una solución obvia.

Observaciones

En el caso de los gráficos, el teorema de Vizing no solo garantiza que el número cromático de borde para un gráfico G sea Δ (G) o Δ (G) +1, las pruebas estándar de este también proporcionan un algoritmo eficiente para encontrar un Δ (G ) + Coloración de 1 borde. Este resultado sería lo suficientemente bueno para mí si estuviera interesado en el caso k = 2; sin embargo, estoy específicamente interesado en k> 2 arbitrario.

Parece que no hay resultados bien conocidos sobre los límites en la coloración del borde de la hipergrafía, a menos que agregue restricciones, como cada borde que se cruza en la mayoría de los vértices. Pero no necesito límites en χ '(H) en sí mismo; solo un algoritmo que encontrará un color de borde "suficientemente bueno". [Tampoco quiero imponer restricciones en mis hipergrafías, excepto por ser uniforme k, y tal vez límites en el grado máximo de vértice, por ejemplo , Δ (H) ≤ f (k) para algunos f ∈ ω (1) .]

[ Addendum. Ahora he hecho una pregunta relacionada en MathOverlow sobre los límites en el número cromático, constructivo o no.]

Niel de Beaudrap
fuente
Parece que este problema a veces se llama empaque de hipergrafía . ¿Ayuda la siguiente página? en.wikipedia.org/wiki/Packing_in_a_hypergraph
Tsuyoshi Ito
Me temo que el artículo de Wikipedia que he vinculado en el comentario anterior puede no ser un buen material para aprender sobre el tema; la terminología es confusa, la misma noción aparentemente se define más de una vez, y así sucesivamente. Espero que alguien conozca un mejor material.
Tsuyoshi Ito
El autor de la pregunta publicó recientemente una pregunta estrechamente relacionada en MathOverflow: mathoverflow.net/questions/38853/… . @Niel de Beaudrap: la próxima vez que vuelva a publicar una pregunta en un lugar diferente, agregue enlaces en ambas direcciones.
Tsuyoshi Ito
@ Tsuyoshi: Gracias por su continuo interés en mi problema. No agregué el enlace de aquí a MO porque el interés en el tema parecía esencialmente haber muerto aquí, sin mucho progreso hacia lo que consideraría una respuesta satisfactoria. (En cualquier caso, volví a vincularme con esta pregunta en la pregunta MO; y la prioridad se puede establecer fácilmente al ver cuándo se hizo). —— No es obvio para mí por qué cree que es importante vincular recíprocamente , antes hay respuestas a la pregunta sobre MO para informar posibles respuestas aquí; pero como me preguntas, lo haré.
Niel de Beaudrap
ΔΘ(Δr)

Respuestas:

3

La respuesta a continuación rompe su condición de que no desea que se impongan restricciones serias a su hipergrafía, pero podría ser de interés solo si se trata de un trabajo relacionado.

rr

Se han realizado algunos trabajos recientes sobre problemas de "coloración colorida" para espacios de rango geométrico, motivados en parte por problemas en las redes de sensores. Una pregunta estándar que se hace es:

kScS(k)cS(k)rSmin(|r|,k)

Por lo tanto, es la cantidad que está buscando (donde es la cardinalidad máxima de un rango).cS(Δ)Δ

Una pregunta relacionada es determinar , donde es el espacio de doble rango (en efecto, su hipergrafía original). Un ejemplo del tipo de resultados obtenidos es que :cS~(k)S~

Para siendo el espacio de en ,S2cS(k)3k2

Una buena referencia para este cuerpo de trabajo es el documento DCG de Aloupsis et al , y sus referencias.

Suresh Venkat
fuente