"All-different hypergraph coloring" - bekanntes Problem?

18

Ich interessiere mich für das folgende Problem: Wenn eine Menge X und Teilmengen X_1, ..., X_n von X gegeben sind, finde eine Färbung der Elemente von X mit k Farben, so dass die Elemente in jedem X_i alle unterschiedlich gefärbt sind. Insbesondere betrachte ich den Fall, in dem alle X_i die Größe k haben. Ist dies in der Literatur unter einem Namen bekannt? Ich suche nach Charakterisierungen von färbbaren Instanzen und Ergebnissen zur Komplexität (P vs. NP-hart). Zum Beispiel entsprechen färbbare Instanzen für k = 2 zweigeteilten Graphen, und somit kann das Problem in Polynomzeit gelöst werden.

Falk Hüffner
quelle
Wenn der Hypergraph Grad D begrenzt hat, ist die maximale
Anzahl
Wenn Sie sich für ein Lehrbuch mit diesen Farbtypen interessieren, besuchen Sie amazon.com/Introduction-Hypergraph-Theory-Vitaly-Voloshin/dp/…. Wenn Sie mehr über Anwendungen der Hypergraph-Färbung erfahren möchten, besuchen Sie paper research.microsoft.com/en-us/um/people/moscitho/Publications/…

Antworten:

14

Ich glaube, dies ist in der Literatur als das Problem bekannt, eine starke k-Färbung für einen k-einheitlichen Hypergraphen zu finden. Dies sollte ein guter Anfang sein: [PDF] .

James King
quelle
10

Es ist auch höchstens so schwer wie die Färbung eines Graphen , wobei gebildet wird, indem jedes zu einer Clique gemacht wird. Ihre Einschränkung, dass alle die Größe bedeutet, dass Sie jede Kante von mit einer Clique auf Ecken abdecken können .kG=(X,E)EXiXikGk

Serge Gaspers
quelle
1
Tatsächlich. Dies sieht aus wie eine Transformation von Covering By Cliques in Garey / Johnson. NP-vollständig für festes , hat aber einen polynomialen Zeitalgorithmus für (wie Falk erwähnt). k3k2
Daniel Apon
2
Die hier vorgeschlagene Konstruktion von ist genau der Gaifman-Graph. G
András Salamon
Korrekt. ist in der Tat der Gaifman-Graph. G
Serge Gaspers
8

Mindestens so hart wie die Färbung eines beliebigen Graphen . Für jede Kante Sie eine Teilmenge ; hier ist jedes ein Dummy-Element, das in keiner anderen Teilmenge vorhanden ist. Wenn Sie Farbe , können Sie leicht eine Färbung des eingestellten Systems finden (färben Sie einfach die Dummy-Elemente gierig ein) und umgekehrt.G = ( V , E ) e = { u , v } X e = { u , v , x ( e , 3 ) , x ( e , 4 ) , ... , x ( e , k ) } x ( e , j ) k GkG=(V,E)e={u,v}Xe={u,v,x(e,3),x(e,4),,x(e,k)}x(e,j)kG

Jukka Suomela
quelle
8

Eine Färbung, bei der jeder Hyperedge polychrom (oder Regenbogen ) ist, wird auch als kräftige Färbung bezeichnet .

Beachten Sie, dass eine starke Färbung eines Hypergraphen genau eine richtige Färbung des Gaifman-Graphen des Hypergraphen ist. (Der Gaifman-Graph (oder der Ur-Graph oder der 2-Abschnitt ) eines Hypergraphen wird durch Hinzufügen von Kanten zwischen zwei beliebigen Scheitelpunkten gebildet, die in einem Hyperedge zusammen auftreten.)

Wenn Sie also nach einer Farbe eines r- einheitlichen Hypergraphen H suchen, können Sie gleichermaßen nach einer k- Farbe des Gaifman-Graphen von H suchen . Der Fall r = 2 entspricht der Graphenfärbung, die für k = 2 polynomial und für k 3 NP-vollständig ist . Offensichtlich ist r < 2 trivial, k < r führt zu keinen Lösungen, und die anderen Fälle sind alle NP-vollständig.krHkHr=2k=2k3r<2k<r

Eine nützliche Referenz, die die meisten der obigen Definitionen aufweist, ist Vitaly I. Voloshin, Coloring Mixed Hypergraphs: Theorie, Algorithmen und Anwendungen , Fields Institute Monographs 17 , AMS, 2002, ISBN 0-8218-2812-6. Dieses Buch behandelt den allgemeineren Fall von schwachen Färbungen, wobei der Schwerpunkt auf der Kombination zweier Arten von farbigen Kanten liegt: Kanten, die mindestens zwei Scheitelpunkte mit einer gemeinsamen Farbe aufweisen, und D- Kanten, die mindestens zwei Scheitelpunkte mit unterschiedlichen Farben aufweisen Farben.CD

András Salamon
quelle
Was würden Sie als Zitat für die NP-Härte des Problems empfehlen? Das obige Buch?
Domotorp
@domotorp nein, das Buch konzentriert sich auf schwache Färbung. Siehe die Antwort von Jukka.
András Salamon