Es gibt wahrscheinlich Tausende von Beispielen; es gibt eine kurze Liste bei ISGCI ; Der Wikipedia-Artikel enthält viele Links. Suchen Sie nach "begrenzter Baumbreite" und "parametrisierter Komplexitätsbaumbreite" für viele, viele mehr.
Im Wesentlichen werden die Probleme bei Graphen mit begrenzter Baumbreite einfach, weil:
Obwohl es NP-vollständig ist, um festzustellen, ob ein Graph höchstens eine Baumbreite hat k [1] gibt es für jeden k Ein linearer Zeitalgorithmus zum Berechnen einer Baumzerlegung eines beliebigen Graphen, der tatsächlich eine Baumbreite aufweist k [2].
Sobald Sie die Baumzerlegung haben, können Sie viele Probleme durch dynamische Programmierung lösen.
Ein einfaches Beispiel, das nicht einmal dynamische Programmierung verwendet, ist das Clique-Problem. Jede Clique eines Graphen muss vollständig in einem Knoten der Baumzerlegung enthalten sein. Das bedeutet, dass ein Diagramm der Baumbreite k kann keine Clique mit einer Größe größer als haben k + 1 und höchstens eine Clique von Größe zu finden k + 1Sie müssen nur sehen, ob jeder Knoten der Zerlegung die gesuchte Clique enthält. Dies kann in linearer Zeit erfolgen, wenn k ist eine feste Konstante, da Sie nur nach Cliquen suchen O ( n ) Grafiken, die jeweils höchstens haben k + 1 Eckpunkte.
Angenommen, Sie möchten wissen, ob es sich um ein Diagramm handelt Gvon Baumbreite 4 ist 3-färbbar. Berechnen Sie zunächst die Baumzerlegung. Jeder Scheitelpunkt des Baumes entspricht einem Teilgraphen von höchstens 5 Scheitelpunkten von G. Berechnen Sie für jedes Blatt des Baumes alle 3-Farben der entsprechenden Untergraphen mit roher Gewalt. Dies ist in Polynomzeit, weil es höchstens gibt n Blätter, jedes entspricht einem Untergraphen mit höchstens 5 Eckpunkten und es gibt höchstens 35= 2433-Farben eines solchen Untergraphen. Nun zu jedem Scheitelpunkt v Zählen Sie des Baums, der an ein Blatt angrenzt, alle 3 Färbungen auf, die mit den möglichen Färbungen der angrenzenden Blätter kompatibel sind v. (Das heißt, die 3-Farben des Untergraphen entsprechen v das kann auf eine 3-Färbung des Graphen entsprechend erweitert werden vund alle angrenzenden Blätter.) An dieser Stelle können Sie die Färbung der Blätter vergessen, da alles, was Sie über sie wissen müssen, jetzt in den Scheitelpunkten Abstand 1 codiert ist. Iterieren Sie nun den Baum. Sie können sich vorstellen, etwas Ähnliches für den Hamilton-Pfad zu tun, indem Sie einen Pfad durch den gesamten Baum erstellen, indem Sie die Pfade in den Teilbäumen zusammenfügen. das ist komplizierter.
[1] Arnborg, Corneil und Proskurowski, "Komplexität beim Auffinden von Einbettungen in einem k-Baum", SIAM Journal on Matrix Analysis and Applications 8 (2): 277–284, 1987. DOI .
[2] Bodlaender, "Ein linearer Zeitalgorithmus zum Auffinden von Baumzerlegungen kleiner Baumbreite", SIAM Journal on Computing 25 (6): 1305–1317, 1996. DOI .
Typischerweise für viele "lokale Probleme" wie zV e r t e x C o v e r oder I n d e p e n d e n t S e t (Dies bedeutet, dass eine Lösung durch Überprüfen der Nachbarschaft jedes Scheitelpunkts überprüft werden kann.) Es werden standardmäßige dynamische Programmiermethoden ausgeführt ctw| V.|O ( 1 ) Zeit, wo tw ist die Baumbreite des Eingabegraphen und c ist eine (kleine) Konstante. Für viele dieser Probleme haben wir übereinstimmende Ober- und Untergrenzen für die Laufzeit der optimalen Lösung, unter der Annahme der sogenannten Strong Exponential Time Hypothesis (SETH).
In gewissem Sinne erscheinen Probleme mit einer "globalen Einschränkung" (wie Konnektivität) schwieriger. Für solche Probleme muss der typische DP-Algorithmus alle Möglichkeiten berücksichtigen, auf die die Lösung den entsprechenden Trenner der Baumzerlegung durchlaufen kann, d. H.Ω (ss) , wo s ist die Größe des Trennzeichens. Weitere Informationen finden Sie hier im FOCS'11-Artikel von Cygan et al., ArXiv-Version . Sie betrachten Monte-Carlo-Algorithmen für Probleme mit globalen Einschränkungen. Es gibt nachfolgende Arbeiten in dieser Richtung, die das "Bedürfnis" nach Zufälligkeit untersuchen.
Sie können sich auch Kapitel 5 von Fomin, Fedor V. und Dieter Kratsch ansehen. Genaue exponentielle Algorithmen. Springer, 2010.
quelle
Vielleicht könnten Sie beginnen mit:
H. Bodlaender und A. Koster, Kombinatorische Optimierung von Graphen begrenzter Baumbreite, The Computer Journal 51 (3), 255-269, 2008.
Fand diese Referenz unter "Ressourcen" von hier .
quelle
Hier ist eine aktuelle Studie zu diesem Phänomen der Baumbreite, das die Komplexität des Problems begrenzt und es aus Sicht der SAT-Instanz (Härte) in P verschiebt. Dies könnte einem größeren Rahmen zugrunde liegen, um die Vereinfachung bei anderen NP-vollständigen Problemen zu verstehen (durch Reduzierung auf SAT).
Starke Hintertüren zu Bounded Treewidth SAT Gaspers / Szeider 2012
quelle