Inkrementelle stark verbundene Komponenten

Für einen sich ändernden gerichteten Graphen möchte ich Informationen über stark verbundene Komponenten pflegen. Die Diagrammoperationen sind inkrementell: nur Scheitelpunktaddition und Kantenaddition. Welche Datenstrukturen erzielen für diese Operationen die bekannteste amortisierte Komplexität?

Wenn der Graph ungerichtet wäre, wäre die Antwort die Union-Find-Struktur. Und da ungerichtete Graphen als Sonderfälle gerichteter Graphen angesehen werden können, überträgt sich die (noch so geringfügige) superkonstante Untergrenze.

Für eine lineare Obergrenze können die stark verbundenen Komponenten nach jeder Kantenaddition von Grund auf neu berechnet werden, ohne dass Daten recycelt werden müssen. Ich frage mich, ob es einen Weg gibt, es besser zu machen.

In der Umgebung, in der ich dies benötige, erwarte ich, dass nicht triviale SCCs eher die Ausnahme als die Regel sind. Und wenn keine Zyklen vorhanden sind, kann ich insgesamt eine lineare Zeit erreichen (dh eine amortisierte konstante Zeit pro Operation). [EDIT:] Lassen Sie mich klarstellen, was ich meine. Natürlich muss ich in Abwesenheit von Zyklen die SCCs überhaupt nicht verfolgen. Die amortisierte konstante Zeit ist für das, was ich in meiner Umgebung mache , außer für die Sorge um SCCs.

Daher würde mich auch Datenstrukturen interessieren, die im Allgemeinen nicht besser als die obige Obergrenze sind, aber eine amortisierte konstante Zeit pro Operation verwenden, solange der Graph eine DAG bleibt.

Nach meinem besten Wissen wird in [1] mit der beste Algorithmus für dekremental stark verbundene Komponenten vorgestellt$O(m \sqrt{n} \log n)$ erwartete Gesamtaktualisierungszeit.

[1] Dekrementelle Erreichbarkeit aus einer Hand und stark verbundene Komponenten in Õ (m√n) Gesamtaktualisierungszeit - Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis - https://ieeexplore.ieee.org / document / 7782945 - FOCS 2016

Update: Der neue beste Algorithmus für dekrementelle SCCs ist $O(m (\log n)^4)$ präsentiert in [5]

[5] Dekrementelle stark miteinander verbundene Komponenten und Erreichbarkeit aus einer Hand in nahezu linearer Zeit - Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen - https://arxiv.org/abs/1901.03615 - akzeptiert auf der STOC 2019

Der beste Algorithmus für inkrementelle stark verbundene Komponenten wird in [2] mit vorgestellt$O(m^{1/2})$ Aktualisierungszeit pro Flanke.

[2] Inkrementelle Zykluserkennung, topologische Reihenfolge und Wartung starker Komponenten - Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan - https://arxiv.org/abs/1105.2397 - 2012 ACM Trans. Algorithmen

Es ist eine offene Frage, ob diese beiden Probleme schneller gelöst werden können.

Für volldynamisch stark verbundene Komponenten sind bedingte Untergrenzen bekannt. Worst-Case-Untergrenzen sind auch für die dekrementelle / inkrementelle Wartung stark verbundener Komponenten bekannt. Einzelheiten finden Sie in [3] und [4].

[3] Vereinheitlichung und Stärkung der Härte für dynamische Probleme mithilfe der Online-Matrix-Vektor-Multiplikations-Vermutung - Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak - https://arxiv.org/pdf/1511.06773.pdf - STOC 2015

[4] Populäre Vermutungen implizieren starke Untergrenzen für dynamische Probleme - Amir Abboud, Virginia Vassilevska Williams - https://arxiv.org/pdf/1402.0054.pdf - FOCS 2014

Alle diese Ergebnisse gelten für allgemeine Diagramme. Bessere Ergebnisse sind für planare Graphen bekannt.

Das Ergebnis, das Sie über DAGs erwähnen, ist bekannt:

Amortisierte Effizienz einer Datenstruktur zum Abrufen von Pfaden - GF Italiano - https://www.sciencedirect.com/science/article/pii/0304397586900988 - TCS 1986