Was unterscheidet einfache globale Probleme von harten globalen Problemen in Diagrammen mit begrenzter Baumbreite?

Viele schwierige Graphenprobleme sind in der Polynomzeit auf Graphen mit begrenzter Baumbreite lösbar . In der Tat verwenden Lehrbücher in der Regel beispielsweise einen unabhängigen Satz als Beispiel, was ein lokales Problem darstellt . Grob gesagt ist ein lokales Problem ein Problem, dessen Lösung überprüft werden kann, indem eine kleine Nachbarschaft jedes Scheitelpunkts untersucht wird.

Interessanterweise können auch Probleme (wie der Hamilton-Pfad) globaler Natur für Diagramme mit begrenzter Baumbreite noch effizient gelöst werden. Für solche Probleme müssen übliche dynamische Programmieralgorithmen alle Wege verfolgen, auf denen die Lösung den entsprechenden Separator der Baumzerlegung durchlaufen kann (siehe z. B. [1]). Randomisierte Algorithmen (basierend auf sogenanntem Cut'n'Count) wurden in [1] angegeben, und verbesserte (sogar deterministische) Algorithmen wurden in [2] entwickelt.

Ich weiß nicht, ob es fair ist, so viele zu sagen, aber zumindest einige globale Probleme können für Diagramme mit begrenzter Baumbreite effizient gelöst werden. Was ist also mit Problemen, die bei solchen Diagrammen hart bleiben? Ich gehe davon aus, dass sie auch globaler Natur sind, aber was noch? Was trennt diese harten globalen Probleme von globalen Problemen , die können effizient gelöst werden? Wie und warum könnten uns bekannte Methoden beispielsweise keine effizienten Algorithmen für diese Methoden liefern?

Beispielsweise könnte man folgende Probleme in Betracht ziehen:

Erweiterung der Kantenvorfärbung Entscheiden Sie bei einem Diagramm mit einigen farbigen Kanten, ob diese Färbung auf eine ordnungsgemäße k- Kanten-Färbung des Diagramms G erweitert werden kann .$G$$k$$G$

Die Kantenvorfärbungserweiterung (und ihre Farbvariante für Listenkanten) ist NP-vollständig für zweigeteilte seriell-parallele Graphen [3] (solche Graphen haben höchstens eine Baumbreite von 2).

Minimale Summenkantenfärbung Bestimme in einem Graphen eine Kantenfärbung χ : E → N, so dass, wenn e 1 und e 2 einen gemeinsamen Scheitelpunkt haben, χ ( e 1 ) ≠ χ ( e 2 ) . Das Ziel ist es, E ' χ ( E ) = ∑ e ∈ E χ ( e ) , die Summe der Färbung, zu minimieren .$G=(V,E)$$\chi : E \to \mathbb{N}$$e_1$$e_2$$\chi(e_1) \neq \chi(e_2)$$E'_\chi(E) = \sum_{e \in E} \chi(e)$

Mit anderen Worten, wir müssen den Kanten eines Graphen positive Ganzzahlen zuweisen, sodass benachbarte Kanten unterschiedliche Ganzzahlen erhalten und die Summe der zugewiesenen Zahlen minimal ist. Dieses Problem ist NP-schwer für partielle 2-Bäume [4] (dh Graphen mit einer Baumbreite von höchstens 2).

Andere derartige schwierige Probleme umfassen das Problem mit kantendisjunkten Pfaden, das Problem mit dem Subgraph-Isomorphismus und das Bandbreitenproblem (siehe z. B. [5] und die darin enthaltenen Referenzen). Informationen zu Problemen, die auch bei Bäumen bestehen bleiben, finden Sie in dieser Frage .

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, JM & Wojtaszczyk, JO (2011, Oktober). Lösen von Konnektivitätsproblemen, die durch die Baumbreite in einer einzelnen Exponentialzeit parametrisiert sind. In Foundations of Computer Science (FOCS), IEEE 52. Jahressymposium 2011 über (S. 150-159). IEEE.

[2] Bodlaender, HL, Cygan, M., Kratsch, S. & Nederlof, J. (2013). Deterministische, einfach exponentielle Zeitalgorithmen für Konnektivitätsprobleme, parametrisiert durch die Baumbreite. In Automaten, Sprachen und Programmierung (S. 196-207). Springer Berlin Heidelberg.

[3] Marx, D. (2005). NP-Vollständigkeit der Listenfärbung und der Vorfärbungserweiterung an den Rändern planarer Graphen. Journal of Graph Theory, 49 (4), 313 & ndash; 324.

[4] Marx, D. (2009). Komplexität ergibt sich für minimale Summenrandfärbung. Discrete Applied Mathematics, 157 (5), 1034 & ndash; 1045.

[5] T. Nishizeki, J. Vygen & X. Zhou (2001). Das Problem der kantendisjunkten Pfade ist für seriell-parallele Graphen NP-vollständig. Discrete Applied Mathematics, 115 (1), 177-186.

Die meisten Algorithmen für Graphen mit begrenzter Baumbreite basieren auf einer Form der dynamischen Programmierung. Damit diese Algorithmen effizient sind, müssen wir die Anzahl der Zustände in der dynamischen Programmiertabelle begrenzen: Wenn Sie einen Polynom-Zeit-Algorithmus möchten, benötigen Sie eine polynomielle Anzahl von Zuständen (z. B. n ^ tw), wenn Sie möchten Um zu zeigen, dass das Problem FPT ist, möchten Sie normalerweise zeigen, dass die Anzahl der Zustände eine Funktion der Baumbreite ist. Die Anzahl der Zustände entspricht normalerweise der Anzahl der verschiedenen Arten von Teillösungen, wenn der Graph bei einem kleinen Trennzeichen unterbrochen wird. Daher ist ein Problem bei Graphen mit begrenzter Breite in der Regel einfach, weil Teillösungen, die mit der Außenwelt über eine begrenzte Anzahl von Scheitelpunkten interagieren, nur eine begrenzte Anzahl von Typen haben. Beispielsweise, in dem unabhängigen Mengenproblem hängt die Art einer Teillösung nur davon ab, welche Grenzscheitelpunkte ausgewählt sind. Im Hamilton'schen Zyklusproblem wird die Art einer Teillösung dadurch beschrieben, wie die Teilpfade der Teillösung die Scheitelpunkte der Grenze aneinander anpassen. Varianten des Courcelle-Theorems geben genügend Bedingungen für ein Problem an, um die Eigenschaft zu haben, dass Teillösungen nur eine begrenzte Anzahl von Typen haben.

Wenn ein Problem bei Diagrammen mit begrenzter Baumbreite schwierig ist, liegt dies normalerweise an einem der folgenden drei Gründe.

1. Es gibt Interaktionen in dem Problem, die vom Diagramm nicht erfasst werden. Steiner Forest ist beispielsweise für Diagramme mit der Breite 3 NP-hart, da die Quelle-Ziel-Paare Interaktionen zwischen nicht benachbarten Scheitelpunkten erzeugen.

Elisabeth Gassner: Das Steiner-Wald-Problem überarbeitet. J. Discrete Algorithms 8 (2): 154-163 (2010)

Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi und Dániel Marx: Approximationsschemata für den Steiner-Wald auf ebenen Graphen und Graphen mit begrenzter Baumbreite. J. ACM 58 (5): 21 (2011)

2. Das Problem wird an den Kanten des Diagramms definiert. Selbst wenn dann ein Teil des Graphen über eine begrenzte Anzahl von Scheitelpunkten an den Rest des Graphen angehängt wird, kann es viele Kanten geben, die auf diese wenigen Scheitelpunkte fallen, und dann kann der Zustand einer Teillösung nur durch Beschreibung des Zustands von beschrieben werden all diese Kanten. Dies machte die Probleme in [3,4] schwer.

3. Jeder Scheitelpunkt kann eine große Anzahl unterschiedlicher Zustände haben. Zum Beispiel ist Capacitated Vertex Cover W [1] -hart durch Baumbreite parametrisiert, intuitiv, da bei der Beschreibung einer Teillösung nicht nur angegeben wird, welche Scheitelpunkte des Separators ausgewählt wurden, sondern auch, wie oft jeder ausgewählte Scheitelpunkt des Separators ausgewählt wurde zum Abdecken von Kanten.

Michael Dom, Daniel Lokshtanov, Saket Saurabh und Yngve Villanger: Kapazitiertes Beherrschen und Bedecken: Eine parametrisierte Perspektive. IWPEC 2008: 78 & ndash; 90

Mein Vorschlag wäre, Courcelles Theorem genau zu betrachten , wonach Probleme, die in (bestimmten Erweiterungen) der monadischen Logik zweiter Ordnung ausgedrückt werden können, FPT-Algorithmen haben, wenn sie durch die Baumbreite parametrisiert werden. Mein Verdacht ist, dass dies viele oder die meisten bekannten Beispiele von FPT-Problemen für diese Diagramme abdeckt. Aus dieser Sicht scheint Ihre lokale / globale Unterscheidung eng mit der Unterscheidung zwischen Problemen, die in existenziellen MSO ausgedrückt werden können, und Problemen zu zusammenhängen, deren MSO-Formulierungen einen höheren Grad an Quantifizierung aufweisen. Um auf Ihre eigentliche Frage zurückzukommen: Das Fehlen einer MSO-Formulierung (die in vielen Fällen unter Verwendung von Ideen im Zusammenhang mit dem Myhill-Nerode-Theorem unbedingt bewiesen werden kann ) wäre ein Beweis für das Fehlen eines FPT-Algorithmus (der ohne komplexitätstheoretische Annahmen schwerer zu beweisen ist).

Ich denke, eines dieser Beispiele ist das spärlichste Schnittproblem. Das Problem des gleichmäßig dünnsten Schnitts ist in Diagrammen mit begrenzter Baumbreite lösbar , das gewichtete Problem des dünnsten Schnitts ist jedoch in Diagrammen mit begrenzter Baumbreite nicht annähernd (besser als 17/16).

Es gibt viele verschiedene Varianten des dünnsten Schnittproblems, aber eine der bekannten ist wie folgt.

$G=(V,E)$$w:E(G)\rightarrow N$$E(S,V\setminus S) \subseteq E(G)$$S \subset V$$\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$$E'\subseteq E(G)$$W(E')=\sum_{e\in E'}w(e)$

Die Hauptzutat besteht aus zwei Dingen:

1. Zusatzfunktionen, wie hier die Gewichtsfunktion. Dennoch gibt es einige Probleme mit der Gewichtsfunktion, die in ungerichteten Diagrammen mit begrenzter Baumbreite nicht sehr schwer sind.

2. Die Natur des dünnsten Schnittproblems. Tatsächliche Existenz von mehr als einer Abhängigkeit für die dynamische Programmierung bei der Definition des Problems. Intuitiv ist die gute Lösung die, dass wir einen Graphen (durch Entfernen einiger Kanten) in zwei nahezu gleiche Größen unterteilen, während wir in dieser Unterteilung so wenige Kanten löschen, wie wir verwenden. Der Grund, warum das Problem in einem Diagramm mit begrenzter Baumbreite so schwer ist, ist, dass wir dynamische Programmierung in zwei Richtungen anwenden sollten, aber beide Richtungen voneinander abhängig sind.

Wenn das Problem so ist, dass mehr als eine Dimension für die dynamische Programmierung erforderlich ist und auch diese Dimensionen voneinander abhängen, kann das Problem in Diagrammen mit begrenzter Baumbreite schwierig sein. Wir können dieses Muster sowohl bei Problemen in der Frage als auch beim dünnsten Schnittproblem beobachten. (Beim ersten Problem wollen wir die vorherige Färbung beibehalten, beim zweiten Problem gibt es offensichtlich zwei Funktionen, die voneinander abhängig sind.)