Ungefähre Graphenfarbe mit einer versprochenen Obergrenze für die maximale unabhängige Menge

In meinem Beruf tritt folgendes Problem auf:

Gibt es einen bekannten Algorithmus, der die chromatische Zahl eines Graphen ohne einen unabhängigen Satz der Ordnung 65 approximiert? (Alpha (G) <= 64 ist also bekannt, und | V | / 64 ist eine triviale untere, | V | eine triviale obere Schranke. Gibt es unter dieser speziellen Bedingung jedoch besser belegte Näherungswerte?)

Was ist, wenn wir uns auf die gebrochene chromatische Zahl entspannen? Und zu "guten" Laufzeiten im Durchschnitt?

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

Ich denke, das ist eine ausgezeichnete Frage für diese Site. Hoffen wir, dass jemand eine gute Antwort hat.

Jukka Suomela

@TysonWilliams: Ich denke, die Frage ist völlig klar. Vergiss den Kommentar, lies die Frage noch einmal. :)

Jukka Suomela

Das Lustige ist, dass diese Bedingung garantiert, dass die triviale Annäherung eine 64-Annäherung an das Optimum ist. Ich frage mich, ob nur das Versprechen einer kleinen Unabhängigkeitszahl einen besseren Algorithmus ergeben kann.

Sasho Nikolov

Ist das Problem durch die praktische Anwendung motiviert? Wenn ja, sollte man sich auf interessante Heuristiken konzentrieren, die gut funktionieren werden - eine Verbesserung der trivialen 64-Approximation ist nicht so interessant.

Chandra Chekuri

Übrigens, wenn Sie schnell gute Annäherungen an die gebrochene chromatische Zahl finden möchten, ist es ausreichend, schnell gute Annäherungen an unabhängige Mengen mit maximalem Gewicht zu finden. Daher schlägt dies eine neue Frage vor: Wenn wir wissen, dass die größte unabhängige Menge die Größe 64 hat, gibt es einen Algorithmus, der gute Näherungen für unabhängige Mengen mit maximaler Gewichtung viel schneller findet als der triviale

-Zeitalgorithmus?

O (n^{64})

$O(n^{64})$

Jukka Suomela

Antworten:

Berechnen Sie eine maximale Übereinstimmung im Komplement des Eingabediagramms. Jeder nicht übereinstimmende Knoten muss in jeder Farbe einer anderen Farbklasse zugeordnet sein. Also: Wenn Sie mindestens cn übereinstimmende Kanten erhalten, erhalten Sie durch das Anpassen selbst eine Färbung mit einer Obergrenze von (1-c) n und einem Näherungsverhältnis von 64 (1-c). Wenn Sie nicht mindestens cn Kanten erhalten, erhalten Sie eine Untergrenze von (1 - 2c) n Farben und ein Näherungsverhältnis von 1 / (1-2c). Die Lösung der Gleichung 64 (1-c) = 1 / (1-2c) führt zu einem Näherungsverhältnis, das etwas größer als 32 ist. Siehe Sasho Nikolovs Kommentar für den genauen Wert.

David Eppstein
quelle

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
quelle

Kleine Korrektur: Es stimmt nicht, dass die Farbzahl der geringsten Anzahl von Farben in einer gierigen Färbung entspricht. Wenn Sie die Scheitelpunkte entsprechend ihrer Farben in einer optimalen Färbung anordnen (mit der zusätzlichen Eigenschaft, dass die erste Farbklasse maximal ist und die zweite in der verbleibenden Grafik maximal usw.), findet der Greedy-Algorithmus dieselbe optimale Färbung.

David Eppstein