Coloration graphique approximative avec une limite supérieure promise sur un ensemble indépendant maximum

Dans mon travail, le problème suivant se pose:

Existe-t-il un algorithme connu, qui se rapproche du nombre chromatique d'un graphique sans un ensemble indépendant d'ordre 65? (Donc alpha (G) <= 64 est connu et | V | / 64 est une borne inférieure triviale, | V | une borne supérieure triviale. Mais y a-t-il de meilleures approximations prouvées dans cette condition spéciale?)

Et si on se détendait au nombre chromatique fractionnaire? Et à de "bons" temps de fonctionnement dans des cas moyens?

ds.algorithms graph-algorithms approximation-algorithms graph-colouring cyrix42
la source

Je pense que c'est une excellente question pour ce site; espérons que quelqu'un a une bonne réponse.

Jukka Suomela

@TysonWilliams: Je pense que la question est parfaitement claire. Oubliez le commentaire, relisez la question. :)

Jukka Suomela

Le plus drôle, c'est que ces conditions garantissent que l'approximation triviale est une approximation de 64 à l'optimum. Je me demande si la promesse d'un petit nombre d'indépendance peut donner un meilleur algorithme.

Sasho Nikolov

Le problème est-il motivé par une application pratique? Si c'est le cas, il faut se concentrer sur des heuristiques intéressantes qui vont bien fonctionner - l'amélioration de l'approximation triviale 64 n'est pas si intéressante.

Chandra Chekuri

Soit dit en passant, si vous voulez trouver rapidement de bonnes approximations du nombre chromatique fractionnaire, il suffit de trouver rapidement de bonnes approximations d'ensembles indépendants de poids maximum. Par conséquent, cela suggère une nouvelle question: si nous savons que le plus grand ensemble indépendant a une taille 64, existe-t-il un algorithme qui trouve de bonnes approximations des ensembles indépendants de poids maximum beaucoup plus rapidement que l' algorithme trivial -temps?

O (n^{64})

$O(n^{64})$

Jukka Suomela

Réponses:

Calculez une correspondance maximale dans le complément du graphique d'entrée. Chaque nœud inégalé doit être dans une classe de couleur différente dans n'importe quelle coloration. Donc: si vous obtenez au moins cn arêtes appariées, alors l'appariement lui-même vous donne une coloration avec une limite supérieure de (1-c) n, et un rapport d'approximation de 64 (1-c). Si vous n'obtenez pas au moins cn bords, alors vous obtenez une limite inférieure de (1 - 2c) n couleurs et un rapport d'approximation de 1 / (1-2c). La résolution de l'équation 64 (1-c) = 1 / (1-2c) conduit à un rapport d'approximation légèrement supérieur à 32; voir le commentaire de Sasho Nikolov pour la valeur précise.

David Eppstein
la source

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$

$H$ $H$

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

Andrew D. King
la source

Correction mineure: il n'est pas vrai que le nombre de colorants soit égal au moins de couleurs dans une coloration gourmande. Si vous commandez les sommets en fonction de leurs couleurs dans une coloration optimale (avec la propriété supplémentaire que la première classe de couleurs est maximale et la seconde est maximale dans le graphique restant, etc.), l'algorithme gourmand trouvera la même coloration optimale.

David Eppstein