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.]
fuente
Respuestas:
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.
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:
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~
Una buena referencia para este cuerpo de trabajo es el documento DCG de Aloupsis et al , y sus referencias.
fuente