Sind Vertexfarben in gewissem Sinne Kantenfarben?

Wir wissen , dass Rand Farbstoffe eines Graphen $G$ sind Vertex Farbstoffe eines speziellen Graphen, nämlich der Liniengraph $L(G)$ von $G$ .

Gibt es ein Graph Operator $\Phi$ so dass Vertex Farbstoffe eines Graphen $G$ sind Kanten Färbungen des Graphen $\Phi(G)$ ? Ich interessiere mich für einen solchen Graphoperator, der in Polynomzeit konstruiert werden kann, dh der Graph $\Phi(G)$ kann aus $G$ in Polynomzeit erhalten werden.

Bemerkung : Eine ähnliche Frage kann für stabile Sets und Matchings gestellt werden. Eine Übereinstimmung in $G$ ist eine stabile Menge in $L(G)$ . Gibt es einen Graphoperator $\Psi$ , bei dem stabile Mengen in $G$ mit übereinstimmen $\Psi(G)$ ? Da STABLE SET ist $\mathsf{ NP}$ -komplette und MATCHING gehört zu $\mathsf{P}$ , wie ein Graph Operator $\Psi$ (falls vorhanden) nicht in Polynomialzeit konstruiert werden, unter der Annahme , $\mathsf{NP}\not=\mathsf{P}$ .

BEARBEITEN: Inspiriert von der Antwort von @ usul und den Kommentaren von @ Okamoto und @ King, fand ich eine schwächere Form für mein Problem: Scheitelpunktfärbungen eines Graphen $G$ sind Kantenfärbungen eines wie folgt definierten Hypergraphen $\Phi(G)$ . Der Scheitelpunkt Satz von $\Phi(G)$ ist die gleiche Knotenmenge von $G$ . Für jeden Eckpunkt $v$ von $G$ ist die geschlossene Nachbarschaft $N_G[v]= N_G(v) \cup\{v\}$ eine Kante des Hypergraphen $\Phi(G)$ . Dann ist das Liniendiagramm des Hypergraphen und daher sind Scheitelpunktfärbungen von Kantenfärbungen von . $G$ $\Phi(G)$ $G$ $\Phi(G)$

Auch hier bin ich dankbar für alle Antworten und Kommentare, die zeigen, dass der von mir Operator mit oder ohne Annahme von nicht existieren kann. Es wäre schön, wenn ich alle Antworten akzeptieren könnte! $\mathsf{NP}\not=\mathsf{P}$

graph-theory graph-algorithms user13136
quelle

Vielen Dank für nette Kommentare (und Geduld!) Und nützliche Antworten. Ich brauche Zeit zum Lesen, zum Nachdenken und komme möglicherweise mit neuen Augen zurück.

user13136

Ich bin auf das folgende sehr interessante Problem von Nishizeki und Zhou im Jahr 1998 gestoßen, das irgendwie mit Ihrer Frage und Ihrem zweiten Kommentar zu @TsuyoshiIto zusammenhängt: Kann das Vertex- Colouring -Problem „einfach“ auf das Edge- Colouring -Problem reduziert werden? (...) Da beide Probleme NP-vollständig sind, kann aufgrund der Theorie der NP-Vollständigkeit eines durch 3-SAT plausibel auf das andere reduziert werden. So fragt das offene Problem, ... (siehe hier )

vb le

@vble: danke! Ich gebe zu, dass ich "zu viel" wollte. Ein solcher Betreiber würde das Problem von Nishizeki und Zhou lösen.

user13136

Antworten:

In Analogie zum Liniendiagramm fragen Sie vermutlich Folgendes:

Für jeden ungerichteten Graphen gibt es einen ungerichteten Graphen so dass jeder Scheitelpunkt einer Kante und entspricht Die Kanten, die und entsprechen, haben genau dann mindestens einen Endpunkt gemeinsam, wenn $G = (V,E)$ $G' = (V',E')$ $v \in V$ $(v_1,v_2) \in E'$ $u \in V$ $v \in V$ ? $(u,v) \in E$

Die Antwort ist nein . Man betrachte den Vier-Eckpunkte-Baum mit der Wurzel mit drei Kindern . In müssen wir vier Kanten haben: . Ferner muss es der Fall sein, dass entweder $G$ $v$ $x,y,z$ $G'$ $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$ $v_1$ oder ist ein Endpunkt jeder der anderen drei Kanten ( dh , , etc). Dies bedeutet jedoch, dass mindestens zwei der anderen drei Kanten einen gemeinsamen Endpunkt haben müssen, was gegen unsere Anforderungen verstößt, da im ursprünglichen Diagramm keine zwei von benachbart sind. $v_2$ $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$ $x,y,z$

Ich denke, die gleiche Grafik gibt Ihnen auch ein Gegenbeispiel für die passende Frage.

usul
quelle

Guter Punkt! Eigentlich hatte ich die gleichen Gedanken. Aber vielleicht gibt es einen anderen Weg, um

zu definieren ? Oder wie können wir formal beweisen , dass ein solcher Operator

nicht existiert?

G^{'}

$G'$

Φ

$\Phi$

user13136

@ user13136, hmm, vielleicht gibt es einen kreativen Weg, aber Sie müssten Ihre Frage umformulieren (ich denke, mein Gegenbeispiel ist ein formaler Beweis für die Frage, wie in der zitierten Box formuliert). Intuitiv denke ich, dass das Problem darin besteht, dass wir in der Richtung des Liniendiagramms eine Kante (die nur mit zwei Scheitelpunkten verbunden werden kann) in einen Scheitelpunkt (der mit einer beliebigen Anzahl von Kanten verbunden werden kann) umwandeln - ganz einfach . Das Gegenteil ist umgekehrt und schwieriger.

USUL

Nur um die Antwort von usul zu ergänzen, lautet die kurze Antwort nein, da Übereinstimmungen strukturelle Eigenschaften aufweisen, die in stabilen Mengen nicht unbedingt vorhanden sind. Beispielsweise ist jedes Liniendiagramm quasi linien- und krallenfrei. Dies schränkt die Tiefe der Kantenfärbungen im Vergleich zu Scheitelpunktfärbungen wirklich ein.

Andrew D. King

Die Frage enthält einige Unklarheiten darüber, was Sie unter „Scheitelpunktfarben eines Graphen G sind Kantenfarben eines Graphen H “ verstehen , aber es ist schwer, einen Graphen zu konstruieren, dessen Kantenfarbzahl gleich der (Scheitelpunkt-) Farbzahl von ist ein gegebenes Diagramm. Formal ist das folgende Beziehungsproblem NP-schwer.

Stellvertretend für chromatische Zahl als Kanten chromatische Zahl
Instanz : Ein Graph G .
Lösung : Ein Graph H, so dass die Farbzahl edge '( H ) von H gleich der Farbzahl χ ( G ) von G ist .

Dies liegt daran, dass das Theorem von Vizing einen (trivialen) effizienten Algorithmus liefert, der die chromatische Kantenzahl innerhalb eines additiven Fehlers von 1 approximiert, wohingegen die chromatische Zahl in verschiedenen Sinnen schwer zu approximieren ist. Zum Beispiel zeigten Khanna, Linial und Safra [KLS00], dass das folgende Problem NP-vollständig ist (und später gaben Guruswami und Khanna [GK04] einen viel einfacheren Beweis):

3-färbbar im Vergleich zu Nicht-4-färbbar
Instanz : Ein Graph G .
Ja-Versprechen : G ist 3-farbig.
Kein Versprechen : G ist nicht 4-farbig.

Dieses Ergebnis reicht aus, um die von mir eingangs behauptete NP-Härte zu belegen. Ein Beweis bleibt als Übung, aber hier ist ein Hinweis:

Übung . Beweisen Sie, dass das oben erwähnte Problem „Darstellen der chromatischen Zahl als kantenchromatische Zahl“ unter polynomieller funktioneller Reduzierbarkeit NP-hart ist, indem Sie „3-färbbar versus Nicht-4-färbbar“ darauf reduzieren. Das heißt, konstruiere zwei Polynomzeitfunktionen f (die einen Graphen auf einen Graphen abbilden) und g (die einen Graphen auf ein Bit abbilden), so dass

Wenn G ein 3-farbiger Graph ist und H ein Graph mit such ( f ( G )) = χ '( H ) ist, dann ist g ( H ) = 1.

Wenn G ein nicht 4-färbbarer Graph ist und H ein Graph ist, bei dem that ( f ( G )) = χ '( H ) ist, dann ist g ( H ) = 0.

Verweise

[GK04] Venkatesan Guruswami und Sanjeev Khanna. Über die Härte von 4-Farben wird ein 3-Farben-Diagramm erstellt. SIAM Journal on Discrete Mathematics , 18 (1): 30–40, 2004. DOI: 10.1137 / S0895480100376794 .

[KLS00] Sanjeev Khanna, Nathan Linial und Shmuel Safra. Auf die Härte der Annäherung der chromatischen Zahl. Combinatorica , 20 (3): 393–415, März 2000. DOI: 10.1007 / s004930070013 .

Tsuyoshi Ito
quelle

Danke für deine Antwort! Ich bin ein bisschen ungenau, indem ich "Scheitelpunktfarben eines Graphen

sind Kantenfarben eines Graphen

" formuliere . Was ich meine, ist ein Operator

wie der Liniendiagrammoperator

, aber von Scheitelpunktfarben bis zu Kantenfarben. Das ist irgendwie mehr als

G

$G$

H

$H$

Φ

$\Phi$

L

$L$

χ (G) = χ^{'} (H)

$\chi(G) = \chi'(H)$

user13136

Da VERTEX COLORING und EDGE COLORING beide

-komplett sind, können wir per Definition

aus

in der Polynomzeit so konstruieren, dass

iff

Aber eine solche Konstruktion muss nicht die Eigenschaft für einen Betreiber erfüllen

ich suche. Es werden nur Scheitelpunktfarben zu Kantenfarben reduziert.

N P

$\mathsf{NP}$

H

$H$

G

$G$

χ (G) \leq k

$\chi(G) \le k$

χ^{'} (H) \leq k^{'}

$\chi'(H) \le k'$

Φ

$\Phi$

user13136

@ user13136: Wenn eine schwächere Anforderung nicht erfüllt werden kann, ist natürlich auch die stärkere Anforderung nicht möglich. Das ist Logik. Sie sollten verstehen, dass Ihr Beispiel für einen planaren Graphen kein Gegenbeispiel dafür ist. Die Entscheidung über die 3-Färbbarkeit eines bestimmten ebenen Graphen ist keine schwächere Voraussetzung als die Entscheidung über die 4-Färbbarkeit eines bestimmten ebenen Graphen. es sind nur unterschiedliche anforderungen. Andererseits habe ich bereits gezeigt, dass das, was Sie wollen, unmöglich ist, es sei denn, P = NP, Punkt. Aber wenn Sie Probleme haben, dies zu verstehen, kann ich Ihnen meines Erachtens nicht weiterhelfen.

Tsuyoshi Ito

Φ

$\Phi$

G = K_{1, 3}

$G=K_{1,3}$

Φ (G)

$\Phi(G)$

G

$G$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$ (seven candidates up to isomorphism), and we will find that the family of edge colorings of

Φ (G)

$\Phi(G)$ and the family of vertex colorings of

G

$G$ are different. A contradiction.

Yoshio Okamoto

@user13136: It occurred to me that you might have been confused because I wrote only a proof idea and I left out the actual proof. I revised the answer so that it would be clear that I left out the actual proof, and added some hints for proof. If this still does not work for you, then I will give up.

Tsuyoshi Ito

(This is an addition to usul's answer and YoshioOkamoto's comment, rather than an answer.) It can be seen that your operation $\Phi$ exists only for those graphs $G$ for which there is a graph $G'$ with $G = L(G')$ , i.e. $G$ is a line graph (checkable in polytime). In this case, $\Phi$ is the "inverse line graph operator" $L^{-1}$ , i.e. $\Phi(G)=G'$ , and vertex colorings of $G$ are edge colorings of $\Phi(G)$ .

In Theory
quelle