Wir haben eine DAG. Wir haben eine Funktion auf den Knoten (wir nummerieren die Knoten). Wir möchten ein neues gerichtetes Diagramm mit diesen Regeln erstellen:
- Nur Knoten mit derselben Nummer können in denselben neuen Knoten eingeteilt werden. . (Allerdings ist .)x ' ≠ y ' ⇏ F ( x ) ≠ F ( y )
- Wir fügen alle alten Kanten zwischen neuen Knoten hinzu: .
- Diese neue Grafik ist immer noch eine DAG.
Was ist das minimale ? Was ist ein Algorithmus, der ein minimales neues Diagramm erstellt?
Antworten:
Ein Ansatz zur Lösung dieses Problems wäre die Verwendung von ILP (Integer Linear Programming). Lassen Sie uns die Entscheidungsversion des Problems angehen: Gibt es bei eine Möglichkeit, Scheitelpunkte gleicher Farbe zu kontrahieren, um eine DAG der Größe ?≤ kk ≤k
Dies kann als ILP-Instanz unter Verwendung von Standardtechniken ausgedrückt werden. Wir erhalten die Farbe jedes Scheitelpunkts im Originaldiagramm. Ich schlage vor, dass wir jeden Scheitelpunkt mit einer Beschriftung in . Alle Scheitelpunkte mit demselben Label und derselben Farbe werden zusammengezogen. Das Entscheidungsproblem lautet also: Gibt es eine Beschriftung, bei der das Zusammenziehen aller Scheitelpunkte mit gleicher Farbe und gleicher Beschriftung eine DAG ergibt?{1,2,…,k}
Um dies als ein ganzzahliges lineares Programm auszudrücken, eine ganzzahlige Variable für jeden Scheitelpunkt , um die Beschriftung auf dem Scheitelpunkt darzustellen . Addiere die Ungleichung . v v 1 ≤ ℓ v ≤ kℓv v v 1≤ℓv≤k
Der nächste Schritt besteht darin, die Anforderung auszudrücken, dass der vertraglich vereinbarte Graph eine DAG sein muss. Beachten Sie, dass bei einer Beschriftung des oben aufgeführten Formulars ohne Einschränkung der Allgemeinheit eine solche Beschriftung vorliegt, bei der die Beschriftungen eine topologische Sortierung in der kontrahierten Grafik auslösen (dh wenn in der kontrahierten Grafik vor , dann die Beschriftung von ) ist kleiner als Etikett). Für jede Kante im Originaldiagramm wird die Bedingung hinzugefügt, dass entweder und dasselbe Label und dieselbe Farbe haben, oder dass das Label von kleiner als das Label von . Insbesondere für jede Kantew v w v → w v w v w v → w v , w l v ≤ l w v → w v , w l v < l wv w v w v→w v w v w v→w im ersten Diagramm, in dem dieselbe Farbe haben, die Ungleichung . für jede Kante für die unterschiedliche Farben haben, die Ungleichung .v,w ℓv≤ℓw v→w v,w ℓv<ℓw
Prüfen Sie nun, ob es eine praktikable Lösung für dieses ganzzahlige lineare Programm gibt. Es wird eine praktikable Lösung nur dann geben, wenn die Beschriftung die gewünschte Form hat (dh wenn alle Scheitelpunkte mit gleicher Farbe und gleicher Beschriftung zusammengezogen werden, ergibt sich eine DAG). Mit anderen Worten, es wird nur dann eine praktikable Lösung geben, wenn es eine Möglichkeit gibt, das ursprüngliche Diagramm auf eine DAG mit der Größe verkleinern . Wir können jeden ganzzahligen linearen Programmierlöser verwenden. Wenn der ILP-Löser uns eine Antwort gibt, haben wir eine Antwort auf das ursprüngliche Entscheidungsproblem.≤k
Natürlich kann dies nicht in polynomieller Zeit garantiert werden. Es gibt keine Garantien. ILP-Solver sind jedoch ziemlich gut geworden. Ich würde erwarten, dass Sie für ein Diagramm mit einer angemessenen Größe eine gute Chance haben, dass ein ILP-Löser dieses Problem in angemessener Zeit lösen kann.
Es ist auch möglich, diese als SAT-Instanz zu codieren und einen SAT-Solver zu verwenden. Ich weiß nicht, ob das effektiver wäre. Die ILP-Version ist jedoch wahrscheinlich einfacher zu überlegen.
(Ich hoffe, das ist richtig. Ich habe nicht jedes Detail sorgfältig geprüft. Bitte überprüfen Sie meine Überlegungen noch einmal! Ich hoffe, ich bin nicht irgendwo schief gegangen.)
Update (21.10.): Es sieht so aus, als ob ILPs dieser Form in linearer Zeit gelöst werden können, indem die DAG in topologisch sortierter Reihenfolge verarbeitet wird und die untere Grenze des Etiketts für jeden Scheitelpunkt verfolgt wird. Das hat mich meiner Lösung verdächtigt: Habe ich irgendwo einen Fehler gemacht?
quelle
HINWEIS: AFAICT, DW hat ein Loch in dieser Reduzierung gefunden und es ist falsch (siehe Kommentare). Es aus historischen Gründen hier zu behalten.
Intro : Zuerst werde ich das Monotone 3SAT Problem auf unser Problem reduzieren. Obwohl das Monotone 3SAT- Problem trivial befriedigend ist, kann unser Problem das NP-harte Minimum True Monotone 3SAT- Problem weiter lösen ; Somit ist dieses Problem NP-schwer.
Reduktion von Monotone 3SAT auf unser Problem
Wir haben eine monotone Boolesche Formel, die als Folge von Variablen und als Folge von Klauseln ausgedrückt wird. Der CNF hat die Form so dass:Φ=(V,C)
Umwandlung
Wir konstruieren einen Graphen, . Jeder Eckpunkt in hat eine Bezeichnung; Scheitelpunkte mit derselben Bezeichnung können kontrahiert werden.G 'G′=V′,E′ G′
Zuerst konstruieren wir das Diagramm wie folgt: Für jedes erstellen wir zwei Knoten mit der Bezeichnung und einer gerichteten Kante von einem zum anderen (klicken Sie auf die Bilder, um eine hochauflösende Ansicht zu erhalten).x ixi∈V xi
Diese Knoten können natürlich zusammengezogen werden, da sie die gleiche Bezeichnung haben. Wir werden Variablen / Knoten, für die ein Vertrag geschlossen wurde, als falsch und solche, für die kein Vertrag geschlossen wurde, als wahr ansehen :
Nach diesem Schritt sollte enthaltenKnoten. Als nächstes führen wir die Klauseleinschränkungen ein. Für jede Klausel wir einen Knoten und ein die folgenden Kanten:V′ 2⋅|V| ci∈C, ci=(xj∨xk∨xl)|xj,xk,xl∈V ci
Beachten Sie, dass die Duplizierung von nur zu dient. Es gibt nur Knoten mit der Bezeichnung . (zum Vergrößern auf das Bild klicken)ci 1 ci
Nach diesem Schritt sollten wirKnoten.2⋅|V|+|C|
Wenn nun , und zusammengezogen werden, führt zu einem Zyklus.xi xj xk ci→ci
Hier ist eine weitere Visualisierung, die die Klauseleinschränkung auflöst:
Daher erfordert jede Klauseleinschränkung, dass mindestens eine der Variablen, die sie enthält, unkontrahiert bleibt. Da die nicht kontrahierten Knoten als wahr bewertet werden, muss eine der Variablen wahr sein. genau das, was Monotone SAT für seine Klauseln benötigt.
Reduktion von Minimum True Monotone 3SAT
Monotone 3SAT ist einfach zu befriedigen; Sie können einfach alle Variablen auf true setzen.
Da unser DAG-Minimierungsproblem darin besteht, die meisten Kontraktionen zu finden, führt dies dazu, dass die zufriedenstellende Zuordnung gefunden wird, die die meisten falschen Variablen in unserem CNF erzeugt. Das ist das Gleiche wie das Finden der minimalen wahren Variablen. Dieses Problem wird manchmal als Minimum True Monotone 3SAT oder hier (als Optimierungs- oder Entscheidungsproblem) oder k-True Monotone 2SAT (als schwächeres Entscheidungsproblem) bezeichnet. beides NP-harte Probleme. Somit ist unser Problem NP-schwer.
Verweise:
Grafikquellen:
quelle
Mit jeder Ersetzung (mit Ausnahme von direkten Eltern-Kind-Ersetzungen) fügen Sie neue Vorfahren-Nachkommen-Beziehungen hinzu, die es nicht trivial machen, zu bestimmen, welche sich langfristig tatsächlich lohnt. Ein einfacher Greedy-Algorithmus schlägt daher im allgemeinen Fall fehl. Wenn Sie jedoch einen Brute-Force-Ansatz verwenden, können Sie den kleinsten Graphen bestimmen:
Python-ish (nicht getestet):
Ich bin mir nicht sicher, ob es wirklich ein schweres Problem ist, aber wenn ich mit einigen Grafiken von Hand spiele, scheint es sehr kombinatorisch zu sein. Ich bin gespannt, ob sich etwas Schwieriges auf dieses Problem reduzieren lässt oder ob es einen Algorithmus mit besserer Laufzeit gibt.
quelle