Randaufteilung in Regenbogendreiecke

Ich frage mich, ob das folgende Problem NP-schwer ist.

Eingabe: ein einfacher Graph und eine Färbung der Kanten ( überprüft keine bestimmte Eigenschaft).$G = (V,E)$$f : E \to \{1,2,3\}$$f$

Frage: Ist es möglich, in Dreiecke zu unterteilen, sodass jedes Dreieck eine Kante jeder Farbe hat?| E | /$E$$|E|/3$

Ich weiß, dass ohne die Farben das Problem der "Kantenpartitionierung" eines Graphen in , NP-hart ist (siehe Die NP-Vollständigkeit einiger Kantenpartitionsprobleme ), aber mit den Farben, die ich nicht kenne. n ≥ $K_n$$n \geq 3$

Ich würde mich auch für ein Ergebnis für die in Regenbogen , wobei eine Konstante ist. In diesem Fall wird das Problem natürlich:$K_c$$c$

Eingabe: ein einfacher Graph und eine Färbung der Kanten ( überprüft keine bestimmte Eigenschaft) .f : E → { 1 , … , c ( c - 1 ) / 2 } $G = (V,E)$$f : E \to \{1,\ldots,c(c-1)/2\}$$f$

Frage: es möglich, in zu unterteilen, so dass jede Clique eine Kante jeder Farbe hat?| E | / ( c ( c - 1 ) / 2 ) K c K $E$$|E|/(c(c-1)/2)$ $K_c$$K_c$

Ich folgte dem Link in der Frage, und die Verkleinerung dort erzeugt tatsächlich Graphen, deren Kanten eine natürliche Färbung haben, so dass jedes in der Grafik vorhandene ein "Regenbogen " ist (hat genau eine Kante jeder Farbe). Mit anderen Worten, wir können die Verkleinerung in diesem Papier leicht so anpassen, dass sie sich auf Ihr Problem reduziert, anstatt sich auf die Partition in Problem zu reduzieren: einfach jeder Kante eine Farbe gemäß dieser natürlichen Farbe zu, und dann kann das Diagramm in unterteilt werden "rainbow s" genau dann, wenn es überhaupt in s unterteilt werden könnte.$K_n$$K_n$$K_n$$K_n$$K_n$

Die Grundstruktur der Reduktion in diesem Papier kann mit den folgenden 3 Schritten erreicht werden:

1. Erstellen Sie viele Kopien eines bestimmten Graphen .$H_{n,p}$
2. Identifizieren Sie bestimmte Teile einiger Kopien von miteinander (dh führen Sie Eckpunkte / Kanten zwischen mehreren verschiedenen Kopien von ).$H_{n,p}$$H_{n,p}$
3. Entfernen Sie bestimmte Scheitelpunkte / Kanten von einigen Kopien.

Der Graph hat als Eckpunkte die Menge der Längen- Vektoren modulo für die die Komponenten zu mod addieren . Die Kanten verbinden alle zwei Eckpunkte, die sich nur in zwei Komponenten unterscheiden, mit Unterschieden von und in diesen beiden Komponenten.$H_{n,p}$$n$$p$$0$$p$$+1$$-1$

Ich schlage für dieses Diagramm die folgende Farbgebung vor: Weisen Sie jeder Kante eine Farbe entsprechend ihrer Richtung zu. Wenn und benachbarte Eckpunkte sind, ist ein Vektor mit Komponenten gleich , einer Komponente gleich und einer Komponente gleich . Mit anderen Worten, für jede Kante gibt es -Optionen, für die Komponenten von ungleich Null sind. Wenn wir jeder dieser Optionen eine eindeutige Farbe zuweisen, haben wir eine Färbung für alle Kanten, sodass jede Kante in derselben Richtung dieselbe Farbe hat. Es ist ziemlich einfach zu überprüfen, ob in einem keine zwei Kanten vorhanden sind$x$$y$$x-y$$n-2$$0$$1$$-1$$(x, y)$${n \choose 2}$$x-y$$K_n$in sind in die gleiche Richtung. Daher ist jedes in ein Regenbogen unter dieser Färbung.$H_{n,p}$$K_n$$H_{n,p}$$K_n$

Wenn wir der Reduktion folgen, verwenden wir diese Färbung für jede Kopie von . Daher ist am Ende von Schritt 1 in der obigen Liste jedes in der Grafik ein Regenbogen .$H_{n,p}$$K_n$$K_n$

In Schritt 2 der obigen Liste identifizieren wir einige Eckpunkte / Kanten miteinander. Insbesondere identifizieren wir bei der Reduktion immer ein mit einem anderen . In dieser Situation (in der alle aus einer Kopie von ) ist jedes entweder eine Übersetzung des "Standard- ", den das Papier nennt, oder eine Übersetzung von . Daher identifizieren wir entweder zwei parallele oder zwei , die "Flips" voneinander sind. In beiden Fällen die Kanten, die über die beiden identifiziert werden$K_n$$K_n$$K_n$$H_{n,p}$$K_n$$K_n$$K$$-K$$K_n$$K_n$$K_n$s sind parallel und haben daher die gleiche Farbe. Siehe zum Beispiel Abbildung 2 im Papier; identifizierte Kanten sind immer parallel. Da wir niemals versuchen, zwei Kanten mit unterschiedlichen Farben zu identifizieren, kann die Färbung am Ende von Schritt 1 in der obigen Liste natürlich zu einer Färbung am Ende von Schritt 2 erweitert werden. Das gemeinsame Identifizieren bestimmter Scheitelpunkte / Kanten führt nicht dazu alle neuen s, so dass es am Ende dieses Schritts immer noch so ist, dass jeder ein Regenbogen .$K_n$$K_n$$K_n$

Schließlich entfernen wir in Schritt 3 einige Eckpunkte / Kanten, wodurch auch keine neuen . Somit haben wir unsere gewünschte Eigenschaft: Unter der von mir angegebenen Färbung ist jedes in der durch diese Reduktion erzeugten Grafik ein Regenbogen .$K_n$$K_n$$K_n$