Algoritmo eficiente para cores de borda quase ótimas de hipergrafos

Os problemas de coloração de gráficos já são difíceis o suficiente para a maioria das pessoas . Mesmo assim, terei que ser difícil e perguntar um problema sobre a coloração hipergráfica.

Questão.

Quais algoritmos eficientes existem para encontrar uma coloração de borda aproximadamente ideal para hipergráficos k uniformes?

Detalhes ---

• Um hipergrafo k-uniforme é aquele em que cada aresta contém exatamente k vértices; o caso usual de um gráfico simples é k = 2. Mais precisamente, eu estou interessado em rotulados hipergrafos k-uniforme, em que dois lados podem realmente têm o mesmo vértice-set; mas vou me contentar com algo em hipergrafos k-regulares com bordas que se cruzam em não mais que k-1 vértices.

• Uma coloração de arestas de hipergrafos é aquela em que arestas da mesma cor não se cruzam, como no caso dos gráficos. O índice cromático χ '(H) é o número mínimo de cores necessárias, como de costume.

• Gostaria de obter resultados em algoritmos de tempo polinomial determinístico ou aleatório.

• Estou procurando o fator de aproximação / intervalo aditivo mais conhecido entre o que pode ser encontrado com eficiência e o índice cromático real χ '(H) --- ou, nesse caso, o melhor resultado possível de ser alcançado em termos de parâmetros como o grau máximo do vértice Δ (H), o tamanho do hipergrafo, etc.

Edit: solicitado pelas observações de Suresh sobre os duais do hipergrafo abaixo, devo observar que esse problema é equivalente ao problema de encontrar uma forte coloração de vértice de um hipergrafo k-regular : ou seja, onde cada vértice pertence a k arestas distintas [mas as arestas agora podem conter números diferentes de vértices], e queremos uma coloração de vértice de forma que quaisquer dois vértices adjacentes tenham cores diferentes. Essa reformulação também parece não ter uma solução óbvia.

Observações

No caso de gráficos, o Teorema de Vizing não apenas garante que o número cromático da borda de um gráfico G seja Δ (G) ou Δ (G) +1, provas padrão também fornecem um algoritmo eficiente para encontrar um Δ (G ) + 1 coloração na borda. Esse resultado seria bom o suficiente para mim se eu estivesse interessado no caso k = 2; no entanto, estou especificamente interessado em k> 2 arbitrário.

Parece não haver resultados conhecidos sobre os limites da coloração da borda do hipergrafo, a menos que você adicione restrições, como todas as arestas que se cruzam no máximo t vértices. Mas não preciso de limites para o χ '(H); apenas um algoritmo que encontrará uma coloração de borda "suficientemente boa". [Eu também não quero impor restrições aos meus hipergrafos, exceto por ser k uniforme, e talvez limitar o grau máximo de vértice, por exemplo , Δ (H) ≤ f (k) para alguns f ∈ ω (1) .]

[ Adendo. Agora eu fiz uma pergunta relacionada no MathOverlow sobre limites no número cromático, construtivo ou não.]

A resposta abaixo quebra sua condição de que você não deseja que restrições sérias sejam impostas ao seu hipergrafo, mas isso pode ser interessante, mesmo que apenas como um trabalho relacionado.

$r$$r$

Houve alguns trabalhos recentes sobre esses problemas de "coloração colorida" para espaços geométricos, motivados em parte por problemas nas redes de sensores. Uma pergunta padrão que é feita é:

$k$$S$$c_S(k)$$c_S(k)$$r$$S$$\min(|r|, k)$

Portanto, é a quantidade que você está procurando (onde é a cardinalidade máxima de um intervalo).$c_S(\Delta)$$\Delta$

Uma questão relacionada é determinar , em que é o espaço de alcance duplo (na verdade, o hipergrafo original). Um exemplo do tipo de resultado obtido é o seguinte :$c_\tilde{S}(k)$$\tilde{S}$

Para sendo o espaço de semiplanos em ,$S$$\Re^2$$c_S(k) \le 3k-2$

Uma boa referência para este corpo de trabalho é o artigo DCG de Aloupsis et al. , E as referências nele contidas.