Coloração aproximada do gráfico com um limite superior prometido no conjunto máximo independente

No meu trabalho, surge o seguinte problema:

Existe um algoritmo conhecido que aproxima o número cromático de um gráfico sem um conjunto independente de ordem 65? (Portanto, alpha (G) <= 64 é conhecido e | V | / 64 é um valor mais baixo trivial, | V | um limite superior trivial. Mas existem aproximações comprovadas melhor sob essa condição especial?)

E se relaxarmos com o número cromático fracionário? E para "bons" tempos de execução em casos médios?

ds.algorithms graph-algorithms approximation-algorithms graph-colouring cyrix42
fonte

Eu acho que essa é uma excelente pergunta para este site; esperamos que alguém tenha uma boa resposta.

Jukka Suomela 19/10/11

@TysonWilliams: Acho que a pergunta é perfeitamente clara. Esqueça o comentário, releia a pergunta. :)

Jukka Suomela 19/10/11

O engraçado é que essas condições garantem que a aproximação trivial seja uma aproximação de 64 ao ideal. Gostaria de saber se apenas a promessa de um pequeno número de independência pode dar um algoritmo melhor.

Sasho Nikolov

O problema é motivado pela aplicação prática? Nesse caso, deve-se focar em heurísticas interessantes que farão bem - melhorar a aproximação trivial não é tão interessante.

Chandra Chekuri 19/10/11

A propósito, se você deseja encontrar boas aproximações do número cromático fracionário rapidamente, é suficiente encontrar boas aproximações de conjuntos independentes de peso máximo rapidamente. Portanto, isso sugere uma nova pergunta: se sabemos que o maior conjunto independente tem tamanho 64, existe um algoritmo que encontra boas aproximações de conjuntos independentes com peso máximo muito mais rápido que o algoritmo trivial de tempo ?

O (n^{64})

$O(n^{64})$

Jukka Suomela 21/10

Respostas:

Calcule uma correspondência máxima no complemento do gráfico de entrada. Cada nó não correspondido deve estar em uma classe de cor diferente em qualquer cor. Portanto: se você obtiver pelo menos arestas correspondidas cn, a correspondência em si fornecerá uma coloração com um limite superior de (1-c) n e uma taxa de aproximação de 64 (1-c). Se você não obtiver pelo menos arestas cn, obterá um limite inferior de (1 - 2c) n cores e uma taxa de aproximação de 1 / (1-2c). Resolver a equação 64 (1-c) = 1 / (1-2c) leva a uma razão de aproximação um pouco maior que 32; veja o comentário de Sasho Nikolov para o valor exato.

David Eppstein
fonte

correção pequena: no primeiro caso, o limite superior é (1-c) n e o limite inferior é n / 64, portanto a razão aproximada é (1-c) 64. Ao resolver (1-c) 64 = 1 / (1-2c), obtém-se e razão de aproximação . Parece que dado um limite superior de para , esse método fornece uma taxa de aproximação que vai para como vai para o infinito.

c = 3 / 16 (4 - \sqrt{2}) \approx 0.5

$c = 3/16 (4-\sqrt{2}) \approx 0.5$

\approx 32

$\approx 32$

k

$k$

α (G)

$\alpha(G)$

\frac{k}{2}

$\frac{k}{2}$

k

$k$

Sasho Nikolov

Você pode estar interessado no número de coloração, que é 1 mais o máximo sobre todos os subgrafos , do grau mínimo de . Ele pode ser calculado com eficiência e é um limite superior para o número cromático. $H$ $H$

http://en.wikipedia.org/wiki/Colouring_number#Algorithms

Andrew D. King
fonte

Correção menor: não é verdade que o número de coloração seja igual ao menor número de cores em uma coloração gananciosa. Se você solicitar os vértices de acordo com suas cores em uma coloração ideal (com a propriedade adicional de que a primeira classe de cores é máxima e a segunda no gráfico restante, etc.), o algoritmo guloso encontrará a mesma coloração ideal.

David Eppstein