NP-Vollständigkeit eines Diagrammfärbungsproblems

Alternative Formulierung

Ich habe eine alternative Formulierung zum folgenden Problem gefunden. Die alternative Formulierung ist eigentlich ein Sonderfall des unten aufgeführten Problems und verwendet zweigeteilte Diagramme, um das Problem zu beschreiben. Ich glaube jedoch, dass die alternative Formulierung immer noch NP-hart ist. Die alternative Formulierung verwendet einen disjunkten Satz eingehender und ausgehender Knoten, der die Problemdefinition vereinfacht.

Gegeben sind ausgehende und n eingehende Knoten (die roten bzw. blauen Knoten in der Figur) und eine Menge w_ {ij} mit der Größe n \ mal n der Kantengewichte zwischen den ausgehenden und eingehenden Scheitelpunkten. Das Ziel des Problems besteht darin, die dicken Kanten in der Figur so zu färben, dass für jeden eingehenden Knoten eine Bedingung gilt.$n$$n$$w_{ij}$$n \times n$

Gegeben eine Menge von Ausgabe-Eckpunkten, eine Menge von Eingabescheitelpunkten, Gewichte zwischen und für und eine positive Konstante , find die minimale Anzahl von Farben für die Kanten (dicke Kanten in der obigen Abbildung), so dass für alle ,$\{ O_i \; | \; i=1 \dots n \}$$\{ I_i\; | \; i=1 \dots n \}$$n \times n$$w_{ij} \ge 0$$O_i$$I_j$$i,j=1 \dots n$$\beta$$e_{ii}$$j=1 \dots n$

$$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta$$

wobei die Farbe der Kante .$c(i)$$e_{ii}$

Alte Formulierung

Das folgende Problem sieht für mich NP-schwer aus, aber ich konnte es nicht zeigen. Jeder Beweis / Kommentar, der die Härte oder Leichtigkeit zeigt, wird geschätzt.

Angenommen, ist ein vollständig gewichteter gerichteter Graph mit Knoten und Kanten. Let zeigen , um das Gewicht der Kante und zeigt die Farbe des Rand . Bei einer Teilmenge der Kanten und einer positiven Konstante das Ziel: Finden Sie die minimale Anzahl von Farben, so dass für jedes :$K_n=\langle V,E \rangle$$n$$n(n-1)$$w_{ij} \ge 0$$ij$$c(ij)$$ij$$T \subseteq E$$\beta$$e_{ij} \in T$

$$\frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta.$$ und $$c(ij) \neq c(ik) \quad for \quad j \neq k$$

Bitte beachten Sie, dass im obigen Problem nur die Kanten in gefärbt werden müssen. Das ist das Problem, das in Gelöst werden kann .$T$$\mathcal{O}(|T|!)$

Aktualisieren:

Nach dem Kommentar von Tsuyoshi Ito habe ich das Problem aktualisiert. Der Nenner wird von in geändert . Daher enthält der Nenner die Gewichte außerhalb als auch. Deshalb habe ich in der Definition das vollständige Diagramm erwähnt.$1+\sum_{c(kj)=c(ij),k \neq i,e_{kj} \in T} w_{kj}$$1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}$$T$

Ich habe auch eine zusätzliche Einschränkung hinzugefügt . Das heißt, die von einem Knoten ausgehenden Kanten müssen unterschiedliche Farben haben (die eingehenden Farben können jedoch gleich sein, solange die Ungleichung gilt). Dies legt eine intuitive Untergrenze für die Anzahl der Farben fest, die der maximale Out-Grad der Knoten in .$c(ij) \neq c(ik) \quad for \quad j \neq k$$T$

Wie Tsuyoshi erwähnte, sind , und Eingaben für das Problem und die Kantenfarben die Ausgabe.$w_{ij}$$T$$\beta$

Update 2:

Das Problem erzwingt nicht, dass die Kanten und dieselbe Farbe haben.$e_{ij}$$e_{ji}$

Es ist ziemlich einfach zu zeigen, dass die alternative Formulierung NP-hart ist. Die Reduzierung ergibt sich aus dem Problem der Scheitelpunktfärbung. Bei einem Graphen G mit Eckpunkten erstellen wir eine Instanz des obigen Problems mit Ausgangsscheitelpunkten und Eingangsscheitelpunkten. Die Gewichte werden wie folgt eingestellt: Für alle sei . Wenn für eine Kante zwischen dem Scheitelpunkt und dem Scheitelpunkt , sei , andernfalls sei . Außerdem sei .$n$$n$$n$$i$$w_{ii}=1$$i \neq j$$i$$j$$w_{ij}=w_{ji}=1$$w_{ij}=w_{ji}=0$$\beta=1$

Dies ist ziemlich offensichtlich, aber schwer zu beschreiben, warum die Reduzierung korrekt ist. Lassen Sie die Instanz der Diagrammfärbung und die reduzierte Instanz des Problems anzeigen. Um zu zeigen, dass die obige Reduktion eine korrekte Lösung ergibt, müssen wir zeigen, dass (1) jede gültige Färbung für auch für gültig ist . (2) Die Antwort von ist für minimal .$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$

Wenn und zwei benachbarte Eckpunkte von , müssen sie in unterschiedliche Farben haben . Das liegt daran, dass wenn und benachbart sind und dieselbe Farbe haben, der Bruch würde zu , wobei einen positiven Wert hat. Daher gilt die Bedingung nicht. Darüber hinaus ist jede gültige (aber nicht unbedingt minimale) Färbung für auch eine gültige Färbung für . Es folgt die Tatsache, dass in einer gültigen Färbung von$i$$j$$\mathcal{C}$$\mathcal{R}$$i$$j$$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$$\frac{1}{1+X}$$X$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$Jedes Paar benachbarter Knoten hat unterschiedliche Farben, sodass die Bedingung für alle farbigen Kanten von in der Lösung gilt. Da jede Färbung von eine gültige Färbung für , muss die minimale Lösung für auch eine minimale Lösung für . Andernfalls handelt es sich nicht um eine minimale Lösung, da die Lösung für eine Lösung mit einer geringeren Anzahl von Farben ergibt.$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{C}$

BEARBEITEN : Die Konstruktion unten funktioniert nicht ganz, wie aus Tsuyoshi Itos Kommentar unten hervorgeht, erzwingt nicht, dass . Ich lasse es für den Fall, dass es ein nützlicher Anfang ist. Außerdem sollte keine Bögen mit dem Gewicht .$c(ij)=c(ji)$$T$$0$

Entlang den Linien Mohsen vorgeschlagen, beginnt mit Kantenfärbung, wandeln den Graphen mit einem Digraph auf der gleichen Eckpunkt wo haben wir und in geben Sie allen Bögen (an diesem Punkt) Gewicht , dann addieren Sie für und zu mit , Set zu und .$G=(V,E)$$D=(V,A)$$\forall uv\in E$$(u,v)$$(v,u)$$A$$a \in A$$w_{a} = 1$$\forall xy \notin E$$(x,y)$$(y,x)$$A$$w_{xy}=w_{yx}=0$$\beta$$1$$T=A$

Dann ist die Bedingung nur erfüllt, wenn keine zwei auf denselben Scheitelpunkt einfallenden Bögen dieselbe Farbe haben, wobei Bögen, die von Nichtkanten im Originaldiagramm stammen (da sie das Gewicht ) , nicht berücksichtigt werden . Diese Farbe kann dann wieder in eine richtige Farbe für das Originaldiagramm umgewandelt werden.$0$

Technisch gesehen habe ich Ihr ursprüngliches Problem in ein Entscheidungsproblem umgewandelt ("Ist der Graph mit Farben färbbar?"), Aber dies musste getan werden, um trotzdem in zu passen, und es ist effektiv bis zu einem Polynom austauschbar.$k$$NP$

Also denke ich, dass das funktioniert, oder habe ich gerade etwas anderes gezeigt, um hart zu sein? ;)$NP$