Incremental strongly connected components

Question

For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data structures achieve the best known amortized complexity for these operations?

If the graph was undirected, the answer would be the union-find structure. And as undirected graphs can be seen as special cases of directed graphs, the (ever so slightly) superconstant lower bound carries over.

For a linear upper bound, the strongly connected components can be computed from scratch after each edge addition, without recycling any data at all. I wonder if there is any way to do better.

In the setting where I need this, I somehow expect non-trivial SCCs to be the exception rather than the rule. And in the absense of cycles I can achieve linear time in total (that is amortized constant time per operation). [EDIT:] Let me clarify what I mean. Of course, in the absense of cycles I do not need to keep track of SCCs at all. The amortized constant time is for what I do in my setting besides worrying abouts SCCs.

So I would also be interested in data structures that are, in general, not better than the above upper bound but use amortized constant time per operation as long as the graph remains a DAG.

Answer 1

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in [1] with $O(m \sqrt{n} \log n)$ total expected update time.

[1] Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time - Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis - https://ieeexplore.ieee.org/document/7782945 - FOCS 2016

Update: The new best Algorithm for decremental SCCs is $O(m (\log n)^4)$ presented in [5]

[5] Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time - Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen -https://arxiv.org/abs/1901.03615 - accepted at STOC 2019

The best algorithm for incremental strongly connected components is presented in [2] with $O(m^{1/2})$ update time per edge.

[2] Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance - Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan -https://arxiv.org/abs/1105.2397 - 2012 ACM Trans. Algorithms

It is an open question if those two problems can be solved faster.

For fully dynamic strongly connected components conditional lower bounds are known. Worst-case lower bounds are also known for decremental/incremental strongly connected component maintenance. For details look in [3] and [4].

[3] Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture - Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak - https://arxiv.org/pdf/1511.06773.pdf - STOC 2015

[4] Popular conjectures imply strong lower bounds for dynamic problems - Amir Abboud, Virginia Vassilevska Williams - https://arxiv.org/pdf/1402.0054.pdf - FOCS 2014

All of these results hold for general graphs. Better results are known for planar graphs.

The result you mention about DAGs is well known:

Amortized efficiency of a path retrieval data structure - G. F. Italiano - https://www.sciencedirect.com/science/article/pii/0304397586900988 - TCS 1986