Graphhomomorphismus - Graph homomorphism

Nicht zu verwechseln mit Graphhomöomorphismus .

Homomorphismus von J5 in C5 grafisch darstellen
Ein Homomorphismus vom Blütenschnatter J 5 in den Zyklusgraphen C 5 .
Es ist auch eine Retraktion auf den Teilgraphen an den zentralen fünf Ecken. Somit ist J 5 tatsächlich dem Kern C 5 homomorph äquivalent .

Im mathematischen Bereich der Graphentheorie ist ein Graphenhomomorphismus eine Abbildung zwischen zwei Graphen , die ihre Struktur respektiert. Genauer gesagt handelt es sich um eine Funktion zwischen den Scheitelpunktmengen zweier Graphen, die benachbarte Scheitelpunkte auf benachbarte Scheitelpunkte abbildet .

Homomorphismen verallgemeinern verschiedene Vorstellungen von Graphfärbungen und ermöglichen den Ausdruck einer wichtigen Klasse von Constraint-Erfüllungsproblemen , wie etwa bestimmten Scheduling- oder Frequenzzuweisungsproblemen . Die Tatsache, dass Homomorphismen zusammengesetzt werden können, führt zu reichhaltigen algebraischen Strukturen: eine Vorordnung auf Graphen, ein Verteilungsgitter und eine Kategorie (eine für ungerichtete Graphen und eine für gerichtete Graphen). Die Rechenkomplexität , einen Homomorphismus zwischen gegebenen Graphen zu finden, ist im Allgemeinen unerschwinglich, aber über Spezialfälle, die in polynomieller Zeit lösbar sind, ist viel bekannt . Grenzen zwischen handhabbaren und hartnäckigen Fällen waren ein aktives Forschungsgebiet.

Definitionen

In diesem Artikel sind Graphen , sofern nicht anders angegeben, endliche, ungerichtete Graphen mit zulässigen Schleifen , aber nicht zulässigen Mehrfachkanten (parallelen Kanten). Ein Graphhomomorphismus f   von einem Graphen G = ( V ( G ), E ( G )) zu einem Graphen H = ( V ( H ), E ( H )), geschrieben

f  : G → H

ist eine Funktion von V ( G ) bis V ( H ), die Endpunkte jeder Kante in G auf Endpunkte einer Kante in H abbildet . Formal impliziert { u , v } E ( G ) { f ( u ), f ( v )} ∈ E ( H ), für alle Knotenpaare u , v in V ( G ). Wenn es irgendwelche Homomorphismus von existiert G bis H , dann G wird gesagt, dass homomorphe zu H oder H -colorable . Dies wird oft nur so bezeichnet:

G → H .

Die obige Definition wird auf gerichtete Graphen erweitert. Dann ist für einen Homomorphismus f  : G → H ( f ( u ), f ( v )) ein Bogen (gerichtete Kante) von H, wenn ( u , v ) ein Bogen von G ist .

Es gibt einen injektiven Homomorphismus von G nach H (dh einen, der niemals unterschiedliche Ecken auf eine Ecke abbildet) genau dann, wenn G ein Teilgraph von H ist . Wenn ein Homomorphismus f  : G → H eine Bijektion (eine Eins-zu-Eins-Entsprechung zwischen den Ecken von G und H ) ist, deren Umkehrfunktion ebenfalls ein Graphenhomomorphismus ist, dann ist f ein Graphenisomorphismus .

Überdeckende Karten sind eine besondere Art von Homomorphismen, die die Definition und viele Eigenschaften von überdeckenden Karten in der Topologie widerspiegeln . Sie sind definiert als surjektive Homomorphismen (dh etwas wird auf jede Ecke abgebildet), die auch lokal bijektiv sind, dh eine Bijektion in der Umgebung jeder Ecke. Ein Beispiel ist die bipartite Doppelüberdeckung , die aus einem Graphen gebildet wird, indem jeder Knoten v in v 0 und v 1 geteilt wird und jede Kante u , v durch Kanten u 0 , v 1 und v 0 , u 1 ersetzt wird . Die Funktion, die v 0 und v 1 in der Abdeckung auf v im ursprünglichen Graphen abbildet, ist ein Homomorphismus und eine überdeckende Abbildung.

Graph homeomorphism ist eine andere Vorstellung, die nicht direkt zu homomorphisms bezogen. Grob gesagt erfordert es Injektivität, ermöglicht aber die Abbildung von Kanten auf Pfade (nicht nur auf Kanten). Graph-Minors sind eine noch entspanntere Vorstellung.

Kerne und Einzüge

Image
K 7 , der vollständige Graph mit 7 Knoten, ist ein Kern.
Hauptartikel: Core (Graphentheorie)

Zwei Graphen G und H sind homomorph äquivalent, wenn G → H und H → G . Die Karten sind nicht unbedingt surjektiv oder injektiv. Zum Beispiel sind die vollständigen bipartiten Graphen K 2,2 und K 3,3 homomorph äquivalent: Jede Abbildung kann so definiert werden, dass sie die linke (bzw. rechte) Hälfte des Domänengraphen nimmt und auf nur einen Knoten in der linken (bzw . rechts) Hälfte des Bilddiagramms.

Ein Zurückziehen ist ein Homomorphismus r aus einem Graphen G auf einen Untergraphen H von G , so daß r ( v ) = v für jeden Scheitelpunkt v von H . In diesem Fall heißt der Teilgraph H ein Retract von G .

Ein Kern ist ein Graph ohne Homomorphismus zu einem echten Teilgraphen. Äquivalent kann ein Kern als ein Graph definiert werden, der sich nicht auf einen richtigen Untergraphen zurückzieht. Jeder Graph G ist homomorph äquivalent zu einem eindeutigen Kern (bis auf Isomorphie), der Kern von G genannt wird . Bemerkenswerterweise gilt dies im Allgemeinen nicht für unendliche Graphen. Dieselben Definitionen gelten jedoch für gerichtete Graphen und ein gerichteter Graph entspricht auch einem eindeutigen Kern. Jeder Graph und jeder gerichtete Graph enthält seinen Kern als Retrakt und als induzierten Teilgraphen .

Zum Beispiel sind alle vollständigen Graphen K n und alle ungeraden Zyklen ( Zyklengraphen ungerader Länge) Kerne. Jeder 3-färbbare Graph G , der ein Dreieck enthält (also den vollständigen Graphen K 3 als Teilgraph hat) ist homomorph äquivalent zu K 3 . Dies liegt zum einen daran, dass eine 3-Färbung von G dasselbe ist wie ein Homomorphismus G → K 3 , wie unten erklärt. Andererseits lässt jeder Teilgraph von G trivialerweise einen Homomorphismus in G zu , was K 3 → G impliziert . Dies bedeutet auch, dass K 3 der Kern eines solchen Graphen G ist . Ebenso ist jeder bipartite Graph mit mindestens einer Kante äquivalent zu K 2 .

Verbindung zu Färbungen

Eine k- Färbung für eine ganze Zahl k ist eine Zuordnung einer von k Farben zu jedem Scheitelpunkt eines Graphen G, so dass die Endpunkte jeder Kante unterschiedliche Farben erhalten. Die k- Färbungen von G entsprechen exakt den Homomorphismen von G zum vollständigen Graphen K k . Tatsächlich entsprechen die Ecken von K k den k Farben, und zwei Farben sind als Ecken von K k genau dann benachbart, wenn sie unterschiedlich sind. Daher definiert eine Funktion einen Homomorphismus zu K k genau dann, wenn sie benachbarte Ecken von G auf verschiedene Farben abbildet (dh sie ist eine k- Färbung). Insbesondere G ist k -colorable , wenn und nur wenn es K k -colorable.

Gibt es zwei Homomorphismen G → H und H → K k , dann ist auch deren Zusammensetzung G → K k ein Homomorphismus. Mit anderen Worten, wenn ein Graph H mit k Farben gefärbt werden kann und es einen Homomorphismus von G zu H gibt , dann kann G auch k- farbig sein. Daher impliziert G → H χ( G ) ≤ χ( H ), wobei χ die chromatische Zahl eines Graphen bezeichnet (das kleinste k, für das es k- färbbar ist).

Varianten

Allgemeine Homomorphismen kann man sich auch als eine Art Färbung vorstellen : Wenn die Ecken eines festen Graphen H die verfügbaren Farben sind und Kanten von H beschreiben, welche Farben kompatibel sind , dann ist eine H- Färbung von G eine Zuordnung von Farben zu Ecken von G so, dass benachbarte Scheitelpunkte kompatible Farben erhalten. Viele Begriffe der Graphenfärbung passen in dieses Muster und können als Graphenhomomorphismen in verschiedenen Graphenfamilien ausgedrückt werden. Kreisförmige Färbungen können unter Verwendung von Homomorphismen zu kreisförmigen vollständigen Graphen definiert werden , was den üblichen Begriff von Färbungen verfeinert. Fractional und b- fold Färbung können unter Verwendung von Homomorphismen in Kneser-Graphen definiert werden . T-Färbungen entsprechen Homomorphismen in bestimmte unendliche Graphen. Eine orientierte Färbung eines gerichteten Graphen ist ein Homomorphismus in jeden orientierten Graphen . Eine L(2,1)-Färbung ist ein Homomorphismus in das Komplement des Pfadgraphen , der lokal injektiv ist, d. h. er muss in der Umgebung jedes Knotens injektiv sein.

Orientierungen ohne lange Wege

Hauptartikel: Gallai–Hasse–Roy–Vitaver-Theorem

Ein weiterer interessanter Zusammenhang betrifft die Orientierungen von Graphen. Eine Orientierung eines ungerichteten Graphen G ist ein beliebiger gerichteter Graph, der durch Auswahl einer der zwei möglichen Orientierungen für jede Kante erhalten wird. Ein Beispiel für eine Orientierung des vollständigen Graphen K k ist das transitive Turnier T → k mit Knoten 1,2,…, k und Bögen von i nach j, wenn i < j . Ein Homomorphismus zwischen den Orientierungen der Graphen G und H ergibt einen Homomorphismus zwischen den ungerichteten Graphen G und H , indem man einfach die Orientierungen vernachlässigt. Andererseits kann bei einem gegebenen Homomorphismus G → H zwischen ungerichteten Graphen jede Orientierung H → von H auf eine Orientierung G → von G zurückgezogen werden, so dass G → einen Homomorphismus zu H → hat . Daher ist ein Graph G ist k -colorable (hat einen Homomorphismus bis K k ) wenn und nur wenn eine Orientierung der G einen Homomorphismus zu hat T → k .

Ein Folklore-Theorem besagt, dass ein gerichteter Graph G für alle k genau dann einen Homomorphismus zu T → k besitzt, wenn er keinen Homomorphismus aus dem gerichteten Pfad P → k +1 zulässt . Dabei ist P → n der gerichtete Graph mit Knoten 1, 2, …, n und Kanten von i nach i + 1, für i = 1, 2, …, n − 1. Ein Graph ist also genau dann k -färbbar wenn es eine Orientierung hat, die keinen Homomorphismus von P → k +1 zulässt . Diese Aussage kann etwas verstärkt werden, indem man sagt, dass ein Graph genau dann k- färbbar ist, wenn irgendeine Orientierung keinen gerichteten Weg der Länge k enthält (kein P → k +1 als Teilgraph). Dies ist der Satz von Gallai-Hasse-Roy-Vitaver .

Verbindung zu Problemen mit der Zufriedenheit mit Einschränkungen

Beispiele

Image
Graph H nicht aufeinanderfolgender Wochentage, isomorph zum Komplementgraphen von C 7 und zur Kreisclique K 7/2

Einige Scheduling-Probleme können als Frage nach dem Finden von Graphenhomomorphismen modelliert werden. Als Beispiel könnte man Workshop-Kurse Zeitfenstern in einem Kalender zuordnen, damit zwei Kurse, die von demselben Studenten besucht werden, zeitlich nicht zu nah beieinander liegen. Die Kurse bilden einen Graphen G mit einer Kante zwischen zwei beliebigen Kursen, die von einem gewöhnlichen Studenten besucht werden. Die Zeitschlitze bilden einen Graphen H mit einer Kante zwischen zwei beliebigen Zeitschlitzen, die zeitlich weit genug entfernt sind. Wenn man zum Beispiel einen zyklischen Wochenplan wünscht, so dass jeder Student seine Workshop-Kurse an nicht aufeinander folgenden Tagen bekommt, dann wäre H der Komplementgraph von C 7 . Ein Graphhomomorphismus von G nach H ist dann ein Zeitplan, der wie angegeben Kurse zu Zeitschlitzen zuweist. Um eine Bedingung hinzuzufügen, dass zB kein einzelner Student sowohl am Freitag als auch am Montag Kurse hat, genügt es, die entsprechende Kante von H zu entfernen .

Ein einfaches Frequenzzuteilungsproblem kann wie folgt spezifiziert werden: Mehrere Sender in einem drahtlosen Netzwerk müssen einen Frequenzkanal wählen, auf dem sie Daten übertragen. Um Störungen zu vermeiden , sollten geografisch nahe Sender Kanäle mit weit auseinander liegenden Frequenzen verwenden. Wenn diese Bedingung mit einem einzigen Schwellenwert angenähert wird, um "geographisch nahe" und "weit auseinander" zu definieren, dann entspricht eine gültige Kanalwahl wieder einem Graphenhomomorphismus. Es sollte von der Kurve der Sender G mit Kanten zwischen geographisch nahen Paaren zu der Kurve der Kanäle H gehen , mit Kanten zwischen den Kanälen, die weit voneinander entfernt sind. Obwohl dieses Modell ziemlich vereinfacht ist, lässt es eine gewisse Flexibilität zu: Senderpaare, die nicht nahe beieinander liegen, aber aufgrund geographischer Merkmale stören könnten, können an den Rändern von G hinzugefügt werden . Diejenigen, die nicht gleichzeitig kommunizieren, können daraus entfernt werden. In ähnlicher Weise können Kanalpaare, die weit voneinander entfernt sind, aber harmonische Interferenzen aufweisen, aus dem Kantensatz von H entfernt werden .

In jedem Fall zeigen diese vereinfachten Modelle viele der Probleme, die in der Praxis behandelt werden müssen. Constraint-Erfüllungsprobleme , die Graphenhomomorphismusprobleme verallgemeinern, können verschiedene zusätzliche Arten von Bedingungen ausdrücken (wie individuelle Präferenzen oder Grenzen für die Anzahl der übereinstimmenden Zuweisungen). Dadurch können die Modelle realistischer und praktischer gestaltet werden.

Formale Ansicht

Graphen und gerichtete Graphen können als Spezialfall des viel allgemeineren Begriffs relationale Strukturen (definiert als Menge mit einem Tupel von Beziehungen darauf) betrachtet werden. Gerichtete Graphen sind Strukturen mit einer einzigen binären Beziehung (Adjazenz) auf der Domäne (der Vertexmenge). Aus dieser Sicht sind Homomorphismen solcher Strukturen exakt Graphenhomomorphismen. Im Allgemeinen ist die Frage, einen Homomorphismus von einer relationalen Struktur zu einer anderen zu finden, ein Constraint Satisfaction Problem (CSP). Der Fall von Graphen gibt einen konkreten ersten Schritt, der hilft, kompliziertere CSPs zu verstehen. Viele algorithmische Methoden zum Auffinden von Graphhomomorphismen, wie Backtracking , Constraint Propagation und Local Search , gelten für alle CSPs.

Für die Graphen G und H entspricht die Frage, ob G einen Homomorphismus zu H hat , einer CSP-Instanz mit nur einer Art von Einschränkung, wie folgt. Die Variablen sind die Ecken von G und der Bereich für jede Variable ist die Eckenmenge von H . Eine Auswertung ist eine Funktion, die jeder Variablen ein Element der Domäne zuordnet, also eine Funktion f von V ( G ) bis V ( H ). Jede Kante oder jeder Bogen ( u , v ) von G entspricht dann der Einschränkung (( u , v ), E( H )). Dies ist eine Bedingung ausdrückt , dass die Auswertung der Lichtbogen Map sollte ( u , v ) zu einem Paar ( f ( u ), f ( v )) , die in der Beziehung E ( H ), die, zu einem Kreisbogen von ist H . Eine Lösung des CSP ist eine Bewertung, die alle Beschränkungen respektiert, also genau ein Homomorphismus von G nach H ist .

Struktur von Homomorphismen

Zusammensetzungen von Homomorphismen sind Homomorphismen. Insbesondere ist die Beziehung → auf Graphen transitiv (und trivialerweise reflexiv), also eine Vorordnung auf Graphen. Die Äquivalenzklasse eines Graphen G unter homomorpher Äquivalenz sei [ G ]. Die Äquivalenzklasse kann auch durch den eindeutigen Kern in [ G ] repräsentiert werden . Die Beziehung → ist eine Teilordnung dieser Äquivalenzklassen; es definiert ein Poset .

Lassen G < H bezeichnen , dass es einen Homomorphismus von ist G bis H , aber kein Homomorphismus von H bis G . Die Beziehung → ist eine dichte Ordnung , was bedeutet , dass für alle (ungerichtet) Graphen G , H , so dass G < H gibt es eine Kurve , K , so dass G < K < H (dies gilt mit Ausnahme der trivialen Fälle G = K 0 oder K 1 ). Zum Beispiel gibt es zwischen zwei beliebigen vollständigen Graphen (außer K 0 , K 1 ) unendlich viele kreisförmige vollständige Graphen , die rationalen Zahlen zwischen natürlichen Zahlen entsprechen.

Das Poset der Äquivalenzklassen von Graphen unter Homomorphismen ist ein Verteilungsgitter , wobei die Verknüpfung von [ G ] und [ H ] definiert ist als (die Äquivalenzklasse von) die disjunkte Vereinigung [ G ∪ H ] und das Treffen von [ G ] und [ H ] definiert als das Tensorprodukt [ G × H ] (die Wahl der Graphen G und H, die die Äquivalenzklassen [ G ] und [ H ] darstellen, spielt keine Rolle). Die verbinden-irreduziblen Elemente dieses Gitters sind exakt zusammenhängende Graphen. Dies lässt sich daran zeigen, dass ein Homomorphismus einen zusammenhängenden Graphen in eine zusammenhängende Komponente des Zielgraphen abbildet. Die treffen-irreduziblen Elemente dieses Gitters sind genau die multiplikativen Graphen . Dies sind die Graphen K, so dass ein Produkt G × H nur dann einen Homomorphismus zu K hat , wenn einer von G oder H dies ebenfalls tut. Die Identifizierung multiplikativer Graphen steht im Mittelpunkt von Hedetniemis Vermutung .

Graphhomomorphismen bilden ebenfalls eine Kategorie mit Graphen als Objekten und Homomorphismen als Pfeile. Das Ausgangsobjekt ist der leere Graph, während das Endobjekt der Graph mit einem Scheitelpunkt und einer Schleife an diesem Scheitelpunkt ist. Das Tensorprodukt von Graphen ist das kategorietheoretische Produkt und der Exponentialgraph ist das Exponentialobjekt für diese Kategorie. Da diese beiden Operationen immer definiert sind, ist die Kategorie der Graphen eine kartesisch geschlossene Kategorie . Aus dem gleichen Grund ist das Gitter der Äquivalenzklassen von Graphen unter Homomorphismen tatsächlich eine Heyting-Algebra .

Für gerichtete Graphen gelten die gleichen Definitionen. Insbesondere → ist eine Teilordnung über Äquivalenzklassen gerichteter Graphen. Sie unterscheidet sich von der Ordnung → auf Äquivalenzklassen ungerichteter Graphen, enthält sie aber als Unterordnung. Dies liegt daran, dass man sich jeden ungerichteten Graphen als einen gerichteten Graphen vorstellen kann, in dem jeder Bogen ( u , v ) zusammen mit seinem inversen Bogen ( v , u ) erscheint, und dies ändert nichts an der Definition des Homomorphismus. Die Ordnung → für gerichtete Graphen ist wiederum ein Verteilungsgitter und eine Heyting-Algebra, wobei Join- und Meet-Operationen wie zuvor definiert sind. Allerdings ist es nicht dicht. Es gibt auch eine Kategorie mit gerichteten Graphen als Objekten und Homomorphismen als Pfeile, die wiederum eine kartesisch geschlossene Kategorie ist .

Unvergleichliche Grafiken

Image
Der Grötzsch-Graphen, unvergleichbar mit K 3

Es gibt viele unvergleichbare Graphen in Bezug auf die Homomorphismus-Vorordnung, dh Paare von Graphen, bei denen keiner einen Homomorphismus in den anderen zulässt. Eine Möglichkeit, sie zu konstruieren, besteht darin, den ungeraden Umfang eines Graphen G zu betrachten , die Länge seines kürzesten Zyklus ungerader Länge. Der ungerade Umfang ist äquivalent die kleinste ungerade Zahl g, für die ein Homomorphismus aus dem Kreisgraphen auf g Ecken zu G existiert . Aus diesem Grunde, wenn G → H , dann ist der ungeradee Umfang G größer oder an den ungeraden Umfang gleich H .

Auf der anderen Seite, wenn G → H , dann ist die Anzahl von chromatischen G kleiner oder gleich der Anzahl von chromatischen H . Wenn G also einen streng größeren ungeraden Umfang als H und eine streng größere chromatische Zahl als H hat , dann sind G und H nicht vergleichbar. Zum Beispiel ist der Grötzsch-Graphen 4-chromatisch und dreiecksfrei (er hat Umfang 4 und ungeraden Umfang 5), ist also mit dem Dreiecksgraphen K 3 nicht vergleichbar .

Beispiele für Graphen mit beliebig großen Werten von ungeradem Umfang und chromatischer Zahl sind Kneser-Graphen und verallgemeinerte Mycielski- Graphen . Eine Folge solcher Graphen mit gleichzeitig steigenden Werten beider Parameter ergibt unendlich viele unvergleichbare Graphen (eine Antikette in der Homomorphismus-Vorordnung). Andere Eigenschaften, wie die Dichte der Homomorphismus-Vorordnung, können mit solchen Familien nachgewiesen werden. Konstruktionen von Graphen mit großen Werten der chromatischen Zahl und des Umfangs, nicht nur ungerader Umfang, sind ebenfalls möglich, aber komplizierter (siehe Umfang und Graphenfärbung ).

Unter gerichteten Graphen ist es viel einfacher, unvergleichliche Paare zu finden. Betrachten Sie zum Beispiel die gerichteten Kreisgraphen C → n , mit Knoten 1, 2, …, n und Kanten von i nach i + 1 (für i = 1, 2, …, n − 1) und von n nach 1. Es ist ein Homomorphismus von C → n zu C → k ( n , k 3) genau dann, wenn n ein Vielfaches von k ist . Insbesondere gerichtete Kreisgraphen C → n mit n prim sind alle unvergleichbar.

Rechenkomplexität

Im Graphenhomomorphismusproblem ist eine Instanz ein Paar von Graphen ( G , H ) und eine Lösung ist ein Homomorphismus von G nach H . Das allgemeine Entscheidungsproblem , das fragt, ob es eine Lösung gibt, ist NP-vollständig . Die Beschränkung der zulässigen Instanzen führt jedoch zu einer Vielzahl verschiedener Probleme, von denen einige viel einfacher zu lösen sind. Methoden, die beim Einspannen der linken Seite G zur Anwendung kommen, sind sehr unterschiedlich als für die rechte Seite H , aber in jedem Fall ist eine Dichotomie (eine scharfe Grenze zwischen leichten und schweren Fällen) bekannt oder vermutet.

Homomorphismen zu einem festen Graphen

Das Homomorphismusproblem mit einem festen Graphen H auf der rechten Seite jeder Instanz wird auch H- Färbungsproblem genannt. Wenn H der vollständige Graph K k ist , ist dies das Graph- k- Farbproblem , das in polynomieller Zeit für k = 0, 1, 2 und ansonsten NP-vollständig lösbar ist . Insbesondere K 2 -colorability eines Graphen G ist äquivalent zu G Wesen bipartite , die in linearer Zeit getestet werden können. Allgemeiner gesagt , wenn H ein zweiteiliger Graph ist, ist die H- Färbbarkeit äquivalent zur K 2 -Färbbarkeit (oder K 0 / K 1 -Färbbarkeit, wenn H leer/kantenlos ist), daher ebenso leicht zu entscheiden. Pavol Hell und Jaroslav Nešetřil haben bewiesen, dass für ungerichtete Graphen kein anderer Fall behandelbar ist:

Hell-Nešetřil-Theorem (1990): Das H- Färbungsproblem liegt in P, wenn H bipartit und ansonsten NP-vollständig ist.

Dies ist auch als Dichotomie-Theorem für (ungerichtete) Graphhomomorphismen bekannt , da es H- Färbungsprobleme in NP-vollständige oder P-Probleme ohne Zwischenfälle unterteilt . Bei gerichteten Graphen ist die Situation komplizierter und tatsächlich äquivalent zu der viel allgemeineren Frage der Charakterisierung der Komplexität von Constraint-Erfüllungsproblemen . Es stellt sich heraus, dass H- Färbungsprobleme für gerichtete Graphen genauso allgemein und so vielfältig sind wie CSPs mit anderen Arten von Einschränkungen. Formal ein (endliches) Constraint Language (oder Vorlage ) Γ eine endliche Domäne und eine endliche Menge von Beziehungen über diese Domain. CSP( Γ ) ist das Constraint-Erfüllungsproblem, bei dem Instanzen nur Constraints in Γ verwenden dürfen .

Theorem (FEDER, Vardi 1998): Für jede Constraint Language Γ , das Problem CSP ( Γ ) entspricht unter Polynom-Zeitverkürzungen bis zu einem gewissen H -coloring Problem, für einige gerichteten Graphen H .

Intuitiv bedeutet dies, dass jede algorithmische Technik oder jedes Komplexitätsergebnis, das auf H- Färbungsprobleme für gerichtete Graphen H zutrifft, auch auf allgemeine CSPs zutrifft. Insbesondere kann man fragen, ob der Hell-Nešetřil-Satz auf gerichtete Graphen erweitert werden kann. Durch die obige Theorem ist dies gleichbedeutend mit der Feder-Vardi Vermutung (aka CSP Vermutung, Dichotomie Vermutung) auf CSP Dichotomie, die diese Sprache für jede Einschränkungs besagt Γ , CSP ( Γ ) NP-vollständig oder in P. Diese Vermutung wurde 2017 unabhängig von Dmitry Zhuk und Andrei Bulatov bewiesen, was zu folgender Folgerung führte:

Korollar (Bulatov 2017; Zhuk 2017): Das H- Färbungsproblem auf gerichteten Graphen ist für ein festes H entweder P- oder NP-vollständig.

Homomorphismen aus einer festen Familie von Graphen

Das Homomorphismusproblem mit einem einzelnen festen Graphen G auf der linken Seite der Eingabeinstanzen kann durch Brute-Force in der Zeit | . gelöst werden V ( H )| O(| V ( G )|) , also Polynom in der Größe des Eingabegraphen H . Mit anderen Worten, das Problem liegt trivialerweise in P für Graphen G beschränkter Größe. Die interessante Frage ist dann, welche anderen Eigenschaften von G neben der Größe polynomiale Algorithmen ermöglichen.

Die entscheidende Eigenschaft stellt sich als treewidth heraus , ein Maß dafür, wie baumartig der Graph ist. Für einen Graphen G der Baumbreite höchstens k und einen Graphen H kann das Homomorphismusproblem in der Zeit | . gelöst werden V ( H )| O( k ) mit einem standardmäßigen dynamischen Programmieransatz . Tatsächlich reicht es aus, anzunehmen, dass der Kern von G höchstens eine Baumbreite k hat . Dies gilt auch, wenn der Kern nicht bekannt ist.

Der Exponent im | V ( H )| O( k ) -Zeitalgorithmus kann nicht signifikant gesenkt werden: kein Algorithmus mit Laufzeit | V ( H )| o(tw( G ) /log tw( G )) existiert unter der Annahme der exponentiellen Zeithypothese (ETH), selbst wenn die Eingaben auf eine beliebige Klasse von Graphen mit unbegrenzter Baumbreite beschränkt sind. Die ETH ist eine unbewiesene Annahme ähnlich P ≠ NP , aber stärker. Unter der gleichen Annahme gibt es auch im Wesentlichen keine anderen Eigenschaften, die verwendet werden können, um polynomielle Zeitalgorithmen zu erhalten. Dies ist wie folgt formalisiert:

Satz ( Grohe ): Für eine berechenbare Klasse von Graphen ist das Homomorphismusproblem für Instanzen mit genau dann in P, wenn Graphen in Kerne beschränkter Baumbreite haben (ETH angenommen).

Man kann sich fragen , ob das Problem zumindest in einer Zeit beliebig stark abhängig von auflösbar ist G , aber mit einem festen Polynom Abhängigkeit von der Größe des H . Die Antwort ist wiederum positiv, wenn wir G auf eine Klasse von Graphen mit Kernen beschränkter Baumbreite beschränken, und negativ für jede andere Klasse. In der Sprache der parametrisierten Komplexität besagt dies formal, dass das Homomorphismusproblem bei der Parametrisierung durch die Größe (Anzahl der Kanten) von G eine Dichotomie aufweist. Es ist mit festen Parametern bearbeitbar, wenn Graphen in Kerne mit begrenzter Baumbreite haben, und W[1] sonst vervollständigen.

Die gleichen Aussagen gelten allgemeiner für Constraint-Erfüllungsprobleme (oder mit anderen Worten für relationale Strukturen). Die einzige erforderliche Annahme besteht darin, dass Beschränkungen nur eine begrenzte Anzahl von Variablen umfassen können (alle Beziehungen haben eine begrenzte Stelligkeit, 2 im Fall von Graphen). Der relevante Parameter ist dann die Baumbreite des primären Constraint-Graphen .

Siehe auch

Anmerkungen

Verweise

Allgemeine Bücher und Ausstellungen

In Beschränkungszufriedenheit und universeller Algebra

In Gittertheorie und Kategorientheorie