Effizienter Algorithmus zur nahezu optimalen Randfärbung von Hypergraphen

Probleme beim Färben von Diagrammen sind für die meisten Menschen bereits schwer genug . Trotzdem muss ich mich schwer tun und ein Problem mit dem Färben von Hypergraphen stellen.

Frage.

Welche effizienten Algorithmen gibt es, um eine annähernd optimale Kantenfärbung für k-einheitliche Hypergraphen zu finden?

Einzelheiten ---

• Ein k-gleichförmiger Hypergraph ist einer, bei dem jede Kante genau k Eckpunkte enthält; der übliche Fall eines einfachen Graphen ist k = 2. Genauer gesagt, ich interessiere mich für beschriftete k-einheitliche Hypergraphen, bei denen zwei Kanten tatsächlich dieselbe Scheitelmenge haben können. aber ich werde mich mit etwas auf k-regulären Hypergraphen zufrieden geben, deren Kanten sich an nicht mehr als k − 1 Eckpunkten schneiden.

• Eine Kantenfärbung von Hypergraphen ist eine Färbung, bei der sich Kanten derselben Farbe nicht schneiden, wie dies bei Diagrammen der Fall ist. Der Buntindex χ '(H) gibt die Mindestanzahl der erforderlichen Farben an.

• Ich hätte gerne Ergebnisse zu deterministischen oder randomisierten polynomiellen Zeitalgorithmen.

• Ich suche nach dem bekanntesten Approximationsfaktor / additiven Spalt zwischen dem, was effizient gefunden werden kann, und dem tatsächlichen chromatischen Index χ '(H) - oder auch nach dem hinsichtlich der Parameter am effizientesten erreichbaren Ergebnis wie der maximale Scheitelpunktgrad & Dgr; (H), die Größe des Hypergraphen usw.

Bearbeiten: Aufgrund von Sureshs Bemerkungen zu Hypergraph-Dualen weiter unten sollte beachtet werden, dass dieses Problem dem Problem entspricht, eine starke Scheitelfärbung eines k-regulären Hypergraphen zu finden: Das heißt, dass jeder Scheitelpunkt zu k verschiedenen Kanten gehört [aber zu den Kanten kann jetzt unterschiedliche Anzahlen von Scheitelpunkten enthalten], und wir möchten eine Scheitelpunktfärbung, sodass zwei benachbarte Scheitelpunkte unterschiedliche Farben haben. Diese Neuformulierung scheint auch keine offensichtliche Lösung zu haben.

Bemerkungen

Im Falle von Graphen garantiert der Satz von Vizing nicht nur, dass die kantenchromatische Zahl für einen Graphen G entweder Δ (G) oder Δ (G) +1 ist, sondern Standardbeweise geben auch einen effizienten Algorithmus zum Auffinden eines Δ (G) ) + 1-Kanten-Färbung. Dieses Ergebnis wäre gut genug für mich, wenn ich mich für den Fall k = 2 interessieren würde; ich interessiere mich aber speziell für k> 2 beliebig.

Es scheint keine bekannten Ergebnisse für Grenzen der Hypergraph-Kantenfärbung zu geben, es sei denn, Sie fügen Einschränkungen hinzu, wie z. B. jede Kante, die sich in höchstens t Scheitelpunkten schneidet. Aber ich brauche keine Grenzen für χ '(H) selbst; nur ein Algorithmus, der eine "gut genug" Kantenfärbung findet. [Ich möchte meine Hypergraphen auch nicht einschränken, außer dass sie k-einheitlich sind, und vielleicht den maximalen Vertex-Grad einschränken, z. B. Δ (H) ≤ f (k) für einige f ω ω (1). .]

[ Nachtrag. Ich habe jetzt bei MathOverlow eine verwandte Frage zu Grenzen der chromatischen Zahl gestellt, sei es konstruktiv oder auf andere Weise.]

Die folgende Antwort unterbricht Ihre Bedingung, dass Sie keine ernsthaften Einschränkungen für Ihren Hypergraphen wünschen, aber es könnte von Interesse sein, wenn auch nur als verwandte Arbeit.

$r$$r$

In jüngster Zeit wurde an solchen "bunten Farbproblemen" für geometrische Bereiche gearbeitet, die teilweise durch Probleme in Sensornetzwerken motiviert sind. Eine Standardfrage, die gestellt wird, ist:

Bestimmen Sie bei gegebenem Parameter und Bereichsraum S die Funktion c S ( k ) so, dass eine c S ( k ) -Färbung der Elemente von S garantiert, dass jeder Bereich r von S hat$k$$S$$c_S(k)$$c_S(k)$$r$$S$$\min(|r|, k)$

Somit, $c_S(\Delta)$$\Delta$

Eine verwandte Frage ist die Bestimmung von $c_\tilde{S}(k)$$\tilde{S}$

$S$$\Re^2$$c_S(k) \le 3k-2$

Eine gute Referenz für dieses Werk ist das DCG-Papier von Aloupsis et al . Und die darin enthaltenen Referenzen.