Gibt es bei einem gewichteten Tag einen O (V + E) -Algorithmus, um jedes Gewicht durch die Summe seiner Vorgängergewichte zu ersetzen?

Das Problem ist natürlich die Doppelzählung. Es ist einfach genug, dies für bestimmte Klassen von DAGs zu tun = einen Baum oder sogar einen Seriell-Parallel-Baum. Der einzige Algorithmus, den ich gefunden habe, um allgemeine DAGs in angemessener Zeit zu bearbeiten, ist ein Näherungsalgorithmus (Synopsis Diffusion), aber die Erhöhung der Genauigkeit ist exponentiell in Bezug auf die Anzahl der Bits (und ich benötige viele Bits).

Hintergrund: Diese Aufgabe wird im Rahmen der Wahrscheinlichkeitsberechnung in BBChop (http://github.com/ealdwulf/bbchop), einem Programm zum Auffinden von zeitweiligen Fehlern (dh einer Bayes-Version von ' git bisect '). Die fragliche DAG ist daher eine Revisionshistorie. Dies bedeutet, dass sich die Anzahl der Kanten wahrscheinlich nicht dem Quadrat der Anzahl der Knoten annähert. Es ist wahrscheinlich, dass sie weniger als das k-fache der Anzahl der Knoten für ein kleines k beträgt. Leider habe ich keine anderen nützlichen Eigenschaften von Revisions-DAGs gefunden. Ich hatte zum Beispiel gehofft, dass die größte dreifach verbundene Komponente nur als Quadratwurzel der Anzahl der Knoten wächst, aber leider (zumindest in der Geschichte des Linux-Kernels) wächst sie linear.

ds.algorithms graph-theory directed-acyclic-graph Ealdwulf
quelle

Nur zur Verdeutlichung: Nur die Knoten haben Gewichte, nicht die Kanten?

Heinrich Apfelmus

Ja, nur die Knoten.

Ealdwulf,

Dies scheint fast ein Duplikat von cstheory.stackexchange.com/questions/553/… zu sein .

Jukka Suomela

Dies scheint tatsächlich allgemeiner zu sein, da das Zuweisen von Einheitsgewichten zu allen Scheitelpunkten dieses Problem auf das Erreichbarkeitsproblem reduziert.

Suresh Venkat

Annäherung scheint nicht schwer zu sein, mit einigen zusätzlichen Polylog-Faktoren ...

Sariel Har-Peled

Antworten:

Wir gehen davon aus, dass es sich bei den Scheitelpunktgewichten um beliebige positive Ganzzahlen handeln kann, genauer gesagt, um positive Ganzzahlen von höchstens 2 ⁿ . Dann kann die aktuelle Aufgabe nicht einmal in einer etwas schwächeren Zeitspanne O ( n ² ) ausgeführt werden, es sei denn, der transitive Abschluss eines willkürlich gerichteten Graphen kann in O ( n ² ) berechnet werden, wobei n die Anzahl der Eckpunkte bezeichnet. (Beachten Sie, dass ein O ( n ² ) -Zeitalgorithmus für den transitiven Verschluss ein Durchbruch sein wird.) Dies ist das Gegenteil der folgenden Behauptung:

Anspruch . Wenn die aktuelle Aufgabe kann in der Zeit O (durchgeführt werden , n ² ), wobei die transitive Schließung eines gerichteten beliebiges Graphen als Adjazenzmatrix gegeben kann in O berechnet werden ( n ² ) Zeit (ein vernünftiges Rechenmodell vorausgesetzt).

Beweis . Als Vorverarbeitung berechnen wir die stark zusammenhängende Komponentenzerlegung des gegebenen gerichteten Graphen G in der Zeit O ( n ² ), um einen DAG G 'zu erhalten. Beachten Sie, dass , wenn wir die transitive Schließung berechnen kann , G ', wir die transitive Schließung rekonstruieren kann G .

Ordnen Sie nun jedem Vertex i der DAG G ' das Gewicht 2 ⁱ zu und verwenden Sie den Algorithmus für das aktuelle Problem. Dann beschreibt die binäre Darstellung der jedem Scheitelpunkt i zugeordneten Summe genau die Menge der Vorfahren von i , mit anderen Worten, wir haben den transitiven Abschluss von G ' berechnet . QED .

Die Umkehrung der Behauptung lautet auch: Wenn Sie den transitiven Abschluss einer bestimmten DAG berechnen können, ist es einfach, die erforderlichen Summen durch zusätzliche Arbeit in Zeit O ( n ² ) zu berechnen . Theoretisch können Sie daher die aktuelle Aufgabe in Zeit O ( n ^2.376 ) ^lösen, indem Sie den Algorithmus für den transitiven Abschluss verwenden, der auf dem Coppersmith-Winograd-Matrixmultiplikationsalgorithmus basiert .

Bearbeiten : Revision 2 und früher haben die Annahme über den Bereich der Scheitelpunktgewichte nicht explizit angegeben. Per Vognsen wies in einem Kommentar darauf hin, dass diese implizite Annahme möglicherweise nicht vernünftig ist (danke!), Und ich stimme zu. Selbst wenn in Anwendungen keine willkürlichen Gewichte benötigt werden, schätze ich, dass diese Antwort einige Ansätze durch die folgende Argumentation ausschließen könnte Die Schließung kann in der Zeit O ( n ² ) berechnet werden . “

Edit : In Revision 4 und früher wurde die Richtung der Kanten falsch angegeben.

Tsuyoshi Ito
quelle

Ich habe letzte Nacht genau darüber nachgedacht, da eine praktische Lösung Bitvektoren verwendet, um die Ausschlusszählung durchzuführen. Ich denke, die einzige Frage ist, ob es vernünftig ist anzunehmen, dass die Gewichte eine Bitlänge proportional zu n haben können. In der Praxis kann ich mir vorstellen, dass die Gewichte durch ein k begrenzt sind, sodass die maximal mögliche Summe kn ist, was nicht ausreicht, um diesen Trick auszuführen.

Per Vognsen,

@Per: Ich stimme zu, dass die Annahme, dass Scheitelpunktgewichte n-Bit-Ganzzahlen sein können, fraglich sein könnte. Ich habe die Antwort bearbeitet, um diese Annahme explizit zu machen. Vielen Dank!

Tsuyoshi Ito

@Per: Ich erkannte, dass, wenn die Scheitelpunktgewichte durch O (1) begrenzt sind, das Problem auf den Fall reduziert wird, in dem alle Scheitelpunkte das Gewicht 1 haben, indem die Scheitelpunkte in geeigneter Weise dupliziert werden.

Tsuyoshi Ito

Leider sehe ich in diesem Thread keine Antwort auf das Zählproblem. Die Zählungen enthalten logarithmisch weniger Informationen als die Auflistung des transitiven Abschlusses, O (n log n) vs O (n ^ 2), sodass ich nicht sehe, wie eine einfache Reduktion funktionieren könnte.

Per Vognsen

Übrigens ist eine interessante Version dieses Problems, wenn wir den Verzweigungsfaktor und Informationen über das Größenwachstum der Generationen (a la topologische Art) der DAG kennen. Wenn das Wachstum exponentiell ist, ist das Muster im Wesentlichen baumartig. Was ist, wenn es linear, logarithmisch linear, quadratisch usw. ist?

Per Vognsen

Dies ist eine Erweiterung meines Kommentars zu Tsuyoshis Antwort. Ich denke, die negative Antwort auf die Frage kann bedingungslos gemacht werden.

$\omega(n)$ $O(n)$

$G_{r,c}$ $r \times c$ $r$ $r$ $c$

$r = (\log\ n)/2$ $c = 2n/\log\ n$

$\sqrt{n}$ $\omega(\log\ n)$

$\omega(n)$ $2c(r-1) = O(n)$

Der Punkt scheint zu sein, dass die zugrunde liegende Teilordnung dicht ist, aber die DAG repräsentiert ihre transitive Reduktion, die spärlich sein kann.

András Salamon
quelle

Dieses Argument ist interessant, aber ich bin nicht sicher, ob es als Beweis für eine interessante Aussage dienen kann. In Anbetracht der allgegenwärtigen Schwierigkeit, untere Grenzen von Problemen zu beweisen, erscheint mir dieses Argument unübersehbar.

Tsuyoshi Ito

@ Tsuyoshi: Ich denke, die Existenz sollte über ein probabilistisches Argument funktionieren, und die untere Schranke ist schwach, also scheint es genug Platz zu geben, damit es funktioniert. Aber Sie haben Recht, es ist handwavy, dass Ausdruck "nicht wiederverwendbare Zusätze im Durchschnitt" eine bessere Grundlage benötigt.

András Salamon

-2

Dies ist falsch und beruht auf einem Missverständnis in der Frage. Vielen Dank an Tsuyoshi, der geduldig auf meinen Fehler hingewiesen hat. Aufgeben, falls andere den gleichen Fehler machen.

$k$

$k$ $O(k|V|)$

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

Dieser Ansatz sollte auch gut funktionieren, wenn es einige Knoten mit vielen unmittelbaren Vorgängern gibt, sofern sie relativ selten sind.

András Salamon
quelle

Ich verstehe es nicht. Wie vermeidet man die Doppelzählung, wenn die DAG kein Baum ist? Wenn ich mich nicht irre, kann der allgemeine Fall auf den Fall reduziert werden, in dem jeder Scheitelpunkt höchstens zwei Vorgänger hat, und jeder Linearzeitalgorithmus für den letzteren Fall gibt einen Zeilenzeitalgorithmus für den allgemeinen Fall an.

Tsuyoshi Ito

O (| V | + | E |)

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

k

$k$

Ich fürchte, Sie haben meinen Kommentar falsch verstanden. Ich frage nach der Richtigkeit Ihres Algorithmus, nicht nach der Laufzeit. Angenommen, eine DAG mit vier Scheitelpunkten A, B, C, D mit Kanten A → B → D und A → C → D, wobei jedem Scheitelpunkt ein gewisses Gewicht gegeben wird. Nach der Berechnung der Teilsummen für B und C können Sie die Teilsummen für B und C nicht einfach addieren, um die Summe für D zu berechnen, da dies das Gewicht des Scheitelpunkts A zweimal addieren würde.

Tsuyoshi Ito

\sum_{u < v} w (u)

$\sum_{u < v} w(u)$

Ja. Und jetzt erinnere ich mich, dass ich die Frage, als ich sie zum ersten Mal sah, auf die gleiche Weise falsch interpretierte und dachte, es wäre offensichtlich. Aber nein, die eigentliche Frage ist schwieriger. Zeit nachzudenken….

Tsuyoshi Ito