Minimale Vertragsgröße einer DAG für eine neue DAG

15

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:F:VN

  1. Nur Knoten mit derselben Nummer können in denselben neuen Knoten eingeteilt werden. . (Allerdings ist .)x 'y 'F ( x ) F ( y )F(x)F(y)xyxyF(x)F(y)
  2. Wir fügen alle alten Kanten zwischen neuen Knoten hinzu: (x,y)Exy(x,y)E .
  3. Diese neue Grafik ist immer noch eine DAG.

Was ist das minimale |V|? Was ist ein Algorithmus, der ein minimales neues Diagramm erstellt?

chx
quelle
1
Das Entscheidungsproblem scheint also zu sein: Wenn eine vertexfarbene DAG und eine ganze Zahl k , entscheidet, ob es eine DAG mit höchstens k Vertices gibt, die durch Kontrahieren von Vertices mit derselben Farbe gebildet werden.
András Salamon
1
Wenn Sie zwei verbundene Knoten unter Vertrag nehmen, erhalten Sie eine verbotene Selbstschleife?
Yuval Filmus
1
Nee. Lesen Sie noch einmal 2.: Wir addieren die Kante nur, wenn die beiden Knoten nach der Kontraktion noch unterschiedlich sind. Wenn zwei Knoten zu einem zusammengezogen werden, wird die Kante nicht hinzugefügt.
chx
1
@chx Fragen Sie nach "minimal" oder "minimum"?
Realz Slaw
1
Kannst du etwas Motivation geben / bkg?
VZN

Antworten:

5

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 ?kkk

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 vkvvv1vk

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 vl w v w v , w l v < l wvwvwvwvwvwvw im ersten Diagramm, in dem dieselbe Farbe haben, die Ungleichung . für jede Kante für die unterschiedliche Farben haben, die Ungleichung .v,wvwvwv,wv<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?

DW
quelle
Danke für die ausführliche Antwort! Ich bekomme die Einschränkungen und sie sehen vernünftig aus. Obwohl ich mit ILP nicht gut vertraut bin, dachte ich, dass die ganzzahlige lineare Programmierung eine Funktion benötigt, die Sie maximieren (oder minimieren) möchten, und ich sehe das nirgendwo. Ich habe nur in Wikipedia eine Gegenprüfung durchgeführt, damit ich mich möglicherweise irre.
chx
@chx, ich benutze ILP, um die Machbarkeit der Einschränkungen zu testen. Dies kann erreicht werden, indem der ILP-Solver aufgefordert wird, eine beliebige Zielfunktion zu maximieren (z. B. 0 zu maximieren), und dann der Wert der Zielfunktion ignoriert wird und nur geprüft wird, ob der ILP durchführbar ist oder nicht. Entweder antwortet der ILP-Solver mit "Infeasible" (was bedeutet, dass es keine vertraglich vereinbarte DAG mit der Größe ), oder er antwortet mit "Feasible" und liefert den besten Wert der gefundenen Zielfunktion. In diesem Fall ignorieren Sie den Wert der Zielfunktion (und Sie wissen, dass es eine DAG mit der Größe ). kkk
DW
Siehe z. B. engineering.purdue.edu/~engelb/abe565/… ("Ich möchte nur wissen, ob es eine praktikable Lösung gibt oder nicht .")
DW
Bezüglich Ihrer linearen Zeitlösung; Ich habe Ihre ILP-Formulierung nicht verdaut, kann sie also nicht beurteilen, aber ich bin mir ziemlich sicher, dass ich beweisen kann, dass das Problem NP-schwer ist, was eine lineare Zeitlösung recht praktisch machen würde: P. Ich werde es bald posten.
Realz Slaw
@ RealzSlaw, danke! In diesem Fall habe ich den starken Verdacht, dass ich mich irgendwo geirrt habe (obwohl ich nicht sicher bin, wo ich mich gerade befinde).
DW
5

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)

(ciC) ci=(xjxkxl)||(xj,xk,xlV)
und

i=1nci|ciC,n=|C|.

Umwandlung

Wir konstruieren einen Graphen, . Jeder Eckpunkt in hat eine Bezeichnung; Scheitelpunkte mit derselben Bezeichnung können kontrahiert werden.G 'G=V,EG

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 ixiVxi

Bildbeschreibung hier eingeben

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 :

Bildbeschreibung hier eingeben

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:V2|V|ciC, ci=(xjxkxl)|xj,xk,xlVci

Bildbeschreibung hier eingeben

Beachten Sie, dass die Duplizierung von nur zu dient. Es gibt nur Knoten mit der Bezeichnung . (zum Vergrößern auf das Bild klicken)ci1ci

Nach diesem Schritt sollten wirKnoten.2|V|+|C|

Wenn nun , und zusammengezogen werden, führt zu einem Zyklus.xixj xkcici

Hier ist eine weitere Visualisierung, die die Klauseleinschränkung auflöst:

Bildbeschreibung hier eingeben

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:

Realz Slaw
quelle
1
Beeindruckend. dann muss die DW-Lösung falsch sein (oder wir haben NP = P bewiesen, was ich zumindest etwas bezweifle: P) - aber wo?
chx
(x1x2x6)(x1x4x5)(x3x4x6)x1=x4=x6=False x2=x3=x5=Truec1x1x4x6c1
@DW Auch schön, wieder mit dir zu reden: D, und viel Glück, wenn wir beide Recht haben, haben wir vielleicht P = NP in deiner Antwort! / jk
Realz Slaw
(x1,x3)
@RealzSlaw, ich fürchte, ich folge noch nicht ... Ich sehe keinen Grund, warum meine Formel konvertiert werden müsste. Ich glaube , es schon ist eine Instanz von Mindest Wahr Monotone 3SAT. Aber lassen Sie mich es auf eine Ebene bringen. Im weiteren Sinne sehe ich eine vorgeschlagene Reduzierung, aber ich sehe kein Argument dafür, dass die Reduzierung korrekt ist - das fehlt. Damit die Reduzierung korrekt ist, müssen YES-Instanzen auf YES-Instanzen und NO-Instanzen auf NO-Instanzen abgebildet werden. Ich vermute, wenn Sie versuchen, einen Beweis für die Richtigkeit Ihrer Kürzung zu schreiben, werden Sie ein Problem bekommen, wenn Sie die Formel betrachten, die ich gegeben habe.
DW
1

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):

def play((V,E),F,sequence=[]):
  """
  (V,E) -- a dag.
  V     -- a set of vertices.
  E     -- a set of directed-edge-tuples.
  F     -- a function that takes a vertex, returns an integer.
  sequence -- the sequence of moved taken so far; starts with/defaults to
              an empty list, will contain tuples of the form (x,y)
              where x is removed and replaced with y.

  Returns the best recursively found solution.
  """

  #find all the integer values in the graph, remember which
  # values correspond to what vertices. Of the form {integer => {vertices}}.
  n2v = {}
  for x in V:
    n = F(x)

    #for each integer, make sure you have a set to put the vertices in.
    if n not in n2v:
      n2v[n] = set()

    #for each integer, add the vertex to the equivalent set.
    n2v[n].add(v)

  #record the best sequence/solution. You start with the current sequence,
  # and see if you can obtain anything better.
  best_solution = list(sequence)

  #Now you will try to combine a single pair of vertices, obtain a new
  # graph and then recursively play the game again from that graph. 

  #for each integer and equivalent set of vertices,
  for n,vset in n2v.iteritems():

    #pick a pair of vertices
    for x in vset:
      for y in vset:

        #no point if they are the same.
        if x == y:
          continue

        #If there is a path from x => y or y => x, then you will be
        # introducing a cycle, breaking a rule. So in that case, disregard
        # this pair.
        #However, the exception is when one is a direct child of the other;
        # in that case you can safely combine the vertices.
        if pathtest((V,E),x,y) and (x,y) not in E and (x,y) not in E:
          continue

        #combine the vertices (function is defined below), discard x,
        # replace it with y, obtain the new graph, (V',E').
        Vp,Ep = combine_vertex((V,E),x,y))

        #record the sequence for this move.
        sequencep = list(sequence) + [(x,y)]

        #recurse and play the game from this new graph.
        solution = play(Vp,Ep,F,sequencep)

        #if the returned solution is better than the current best,
        if len(solution) > len(best_solution):
          #record the new best solution
          best_solution = solution
  #return the best recorded solution
  return best_solution


def combine_vertex((V0,E0),x,y):
  """
  (V0,E0)   -- an initial digraph.
  V0        -- a set of vertices.
  E0        -- a set of directed-edge-tuples.
  x         -- vertex to discard.
  y         -- vertex to replace it with.

  returns a new digraph replacing all relationships to and from x to relate
   to y instead, and removing x from the graph entirely.
  """

  #the final vertex set will have everything except x
  V = set(V0)
  V.discard(x)

  #now you construct the edge set.
  E = set()

  #for every edge,
  for (u0,v0) in E0:
    #recreate the edge in the new graph, but replace any occurence
    # of x.  
    u,v = u0,v0
    #if x is in the edge: replace it
    if u == x:
      u = y
    if v == x:
      v == y

    #sometimes u=v=y and can now be pointing to itself, don't add that
    # edge
    if u == v:
      continue

    #add the new/replaced edge into the edge-set.
    E.add( (u,v) )
  return (V,E)

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.

Realz Slaw
quelle
1
Ich bin auch neugierig :)
chx