Transitive Reduktion der DAG

13

Ich suche einen O (V + E) -Algorithmus, um die transitive Reduktion bei gegebener DAG zu finden.

Das heißt, entfernen Sie so viele Kanten wie möglich, so dass Sie nach dem Entfernen der Kanten immer noch nach v greifen können, wenn Sie v von u aus für willkürliches v und u erreichen könnten.

Wenn dies ein Standardproblem ist, weisen Sie mich bitte auf eine Modelllösung hin.

algorithms graphs dag Karan
quelle

Sie können den in dem von Ihnen zitierten Wikipedia-Lemma angegebenen Verweis nicht verwenden?

Hendrik Jan

2

Nun, der in der Wikipedia diskutierte Algorithmus läuft wie gewünscht in

(im besten Fall, dh im Fall von azyklischen Graphen) anstelle von

. Ich denke, die richtige Antwort ist, dass der gesuchte Algorithmus möglicherweise nicht existiert

O (V \times E)

$O(V\times E)$

O (V + E)

$O(V+E)$

Carlos Linares López

1

Einverstanden, dass es nicht klar ist, dass das, wonach Sie fragen, existiert. Es gibt eine ganze Reihe von Artikeln, die ohne einen solchen Algorithmus nicht interessant wären, z. B. sciencedirect.com/science/article/pii/0012365X9390164O . Das heißt, wenn Sie genauer wissen, was Ihre Motivation ist, gibt es möglicherweise spezifischere Lösungen. Wissen Sie zum Beispiel noch etwas über den Graphen oder würde

funktionieren?

O (n (n + m))

$O(n(n+m))$

William Macrae

Ich habe das Problem irgendwo gesehen, aber es gab keine zusätzlichen Informationen, vielleicht einen Tippfehler im Problem.

Karan

1

Was passiert , wenn Sie in Ihrem DAG topologische Sortierung, aber Spur von erreichbaren Ecken halten von Kindern verwendet wird , dh

r e a c h a b l e [v] = \cup_{v^{'} \in c h i l d r e n_{v}} r e a c h a b l e [v^{'}]

$reachable[v] = \cup_{v' \in children_v} reachable[v']$ Wenn Sie mit dem neuesten Element in der sortierten Grafik beginnen, nicht verwendete Kanten entfernen und die erreichbare Funktion beibehalten, können Sie maximal mögliche Kanten entfernen. Ich bin mir jedoch nicht sicher, ob die maximale Wahrscheinlichkeit erreicht wird (es ist

.

O (| E | + | V |)

$O(|E|+|V|)$

8

Wir können dieses Problem lösen, indem wir DFS von jedem Scheitelpunkt aus ausführen.

Starten Sie für jeden Scheitelpunkt die DFS von jedem Scheitelpunkt , sodass der direkte Nachkomme von , d. H. ist eine Kante. $u \in G$ $v$ $v$ $u$ $(u,v)$
Entfernen Sie für jeden Scheitelpunkt den die DFS von kann, die Kante . $v'$ $v$ $(u, v')$

Die Gesamtkomplexität des Obigen ist die Komplexität des Ausführens von DFS ', was . $N$ $O(N(N+M))$

Pratyaksh
quelle

1

Beachten Sie, dass dies asymptotisch die gleiche Komplexität aufweist wie der

-Algorithmus im Wikipedia-Artikel, der in der Frage selbst verlinkt ist.

O (N M)

$O(NM)$

David Richerby

1

Einverstanden. Da für diese Frage eine präzise Antwort fällig war, habe ich eine vorgelegt. Ferner ist eine

-Lösung nach IMO unwahrscheinlich.

O (N)

$O(N)$

Pratyaksh

3

Nicht das, wonach Sie suchen. Aber nur zum Zweck des Wissensaustauschs können Sie dies mit Nachrichten tun, wenn Sie davon ausgehen, dass jeder Eckpunkt als Prozessor fungiert . Beachten Sie, dass jeder Scheitelpunkt einen vergleichbaren Wert hat. Daher gibt es einige Eckpunkte, die größer sind als alle ihre Nachbarn. Diese Eckpunkte führen Folgendes aus: $O(|E|)$

Sei der maximale kleinere Nachbar von , $u$ $v$
sende eine Nachricht an und füge edge in die Ausgabe ein. $u$ $(v,u)$
Beziehen Sie für jeden Nachbarn von und (und kleiner als beide) in die Ausgabe ein. $w$ $u$ $v$ $(v,w)$
Wiederholen Sie die Schritte, bis alle Kanten für einen kleineren Nachbarn des Scheitelpunkts entweder in der Ausgabe enthalten sind oder nicht. $(v,v')$ $v'$ $v$

Wenn nun ein Knoten eine Nachricht von jedem größeren Nachbarn empfangen hat (dh alle Kanten sind entweder enthalten oder nicht enthalten), verhält sich der Knoten , als ob er der größte in seiner Nachbarschaft wäre zuvor erwähnten 4 Schritte. $v$ $(v',v)$ $v$

Dieser Algorithmus endet in Nachrichten in einer verteilten Umgebung. Ich weiß, das ist nicht das, wonach du fragst. $O(|E|)$

AJed
quelle

1

Lemma: Wenn es eine Kante V -> Y gibt und Y auch ein indirekter Nachfolger von V ist (z. B. V -> W -> + Y), dann ist die Kante V -> Y transitiv und nicht Teil der transitiven Wurzel.

Methode: Verfolgen Sie den transitiven Abschluss jedes Scheitelpunkts, indem Sie in umgekehrter topologischer Reihenfolge vom Endpunkt zum Anfangsscheitelpunkt arbeiten. Die Menge der indirekten Nachfolger von V ist die Vereinigung der transitiven Abschlüsse der unmittelbaren Nachfolger von V. Die transitiven Abschlüsse von V sind die Vereinigung ihrer indirekten Nachfolger und ihrer unmittelbaren Nachfolger.

Algorithmus:

    Initialise Visited as the empty set.
    For each vertex V of G, 
        Invoke Visit(V).

    Visit(V):
        If V is not in Visited,
            Add V to Visited, 
            Initialise Indirect as the empty set,
            For each edge V -> W in G,
                Invoke Visit(W),
                Add Closure(W) to Indirect.
            Set Closure(V) to Indirect.
            For each edge V -> W in G,
                Add W to Closure(V),
                If W is in the set Indirect,
                    Delete the edge V -> W from G.

Dies setzt voraus, dass Sie einen effizienten Weg haben, um Verticesätze (z. B. Bitmaps) zu verfolgen, aber ich denke, diese Annahme wird auch in anderen O (V + E) -Algorithmen getroffen.

Ein potenziell nützlicher Nebeneffekt ist, dass er den transitiven Verschluss jedes Scheitelpunkts von G findet.

DrBD
quelle

Ich habe die Antwort auf Ihrem früheren Konto gelöscht. Wenn Sie Ihre beiden Konten dennoch zusammenführen möchten, befolgen Sie die Schritte in der Hilfe . Das heißt, da der frühere Account keinen sichtbaren Inhalt mehr hat, können Sie sich einfach an den neuen halten.

Gilles 'SO - hör auf böse zu sein',

0

Ich habe das gleiche Problem gelöst, aber es war nicht genau dasselbe. Es wurde nach der Reduzierung nach dem Minimum an Kanten im Diagramm gefragt, sodass die ursprünglich verbundenen Scheitelpunkte weiterhin verbunden sind und keine neuen Verbindungen hergestellt werden. Es ist klar, dass es nicht heißt, den verkleinerten Graphen zu finden, sondern wie viele redundante Kanten vorhanden sind. Dieses Problem kann mit O (V + E) gelöst werden. Der Link zur Erklärung lautet https://codeforces.com/blog/entry/56326 . Aber ich denke, um das Diagramm tatsächlich zu machen, wird es eine höhere Komplexität haben als O (N).

Kumar Mohit
quelle

Transitive Reduktion der DAG

Antworten: