<p>I know it is an older question but this research paper has a relatively straight forward O(m^(3/2)) algorithm for incrementally maintaining them: <a href="https://arxiv.org/pdf/1105.2397.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1105.2397.pdf</a>
Here is one with O(m) algorithm for decrementally maintaining them: <a href="https://arxiv.org/pdf/1901.03615.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1901.03615.pdf</a> (from 2019 and it improves on the O(m*sqrt(n)) algorithm of <a href="https://u.cs.biu.ac.il/%7Eliamr/scc-new.pdf" rel="nofollow noreferrer">https://u.cs.biu.ac.il/~liamr/scc-new.pdf</a>)</p>
<p>I am not sure there is anything better for doing both operations.  Part of the issue is the data structure used for maintaining them.  Incremental algorithms are typically using Tarjan's Union-Find for fast partitioning of disjoint sets.  While decremental algorithms are using an Even-Shiloach(ES)-tree, as the breadth-first-search representation matches the problem.</p>
<p>As for a unified data structure which efficiently can be used for a fully online SCC maintenance, that would be progress we hope to see soon.</p>

CC BY-SA 4.0
2020-07-20T04:12:11.340Z
2020-07-20T04:12:11.340Z
Gregory Morse
<p>I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices.</p>

<p>As noted in one of the answers to a closely-related question <a href="https://cstheory.stackexchange.com/questions/11696">here</a>, the literature in this area is rather fragmented and hard for a newcomer such as myself to approach.</p>

<p>For example, the <a href="http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/polylogarithmic.pdf" rel="nofollow noreferrer">paper by Holm et al.</a> appears to focus on undirected graphs, and it's unclear to me whether any of their results can be adapted to work with digraphs.  Other papers I've found focus on either the incremental or decremental cases, rather than the fully-dynamic case.</p>

<p>My need arises in a real-world software engineering scenario, so I would actually be fine with an approach that yields no worst-case asymptotic advantage over the naive idea of running an SCC algorithm from scratch for each update, so long as it performs well in practice.</p>

<p>I'd prefer not to reinvent the wheel, but I also don't have endless hours to wade through the literature, so hopefully someone here can save me some time.</p>

<p>Thanks in advance!</p>

<graph-algorithms>
Fully dynamic algorithms for strong components of a directed graph
factotum
# Fully dynamic algorithms for strong components of a directed graph

(Asked by: username_0 on 2014-11-14)

I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices.

As noted in one of the answers to a closely-related question [here](https://cstheory.stackexchange.com/questions/11696), the literature in this area is rather fragmented and hard for a newcomer such as myself to approach.

For example, the [paper by Holm et al.](http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/polylogarithmic.pdf) appears to focus on undirected graphs, and it's unclear to me whether any of their results can be adapted to work with digraphs. Other papers I've found focus on either the incremental or decremental cases, rather than the fully-dynamic case.

My need arises in a real-world software engineering scenario, so I would actually be fine with an approach that yields no worst-case asymptotic advantage over the naive idea of running an SCC algorithm from scratch for each update, so long as it performs well in practice.

I'd prefer not to reinvent the wheel, but I also don't have endless hours to wade through the literature, so hopefully someone here can save me some time.

Thanks in advance!

**Tags:** graph-algorithms


---

## 1 answers

### Answer by username_1 on 2020-07-20. Score: 1

I know it is an older question but this research paper has a relatively straight forward O(m^(3/2)) algorithm for incrementally maintaining them: <https://arxiv.org/pdf/1105.2397.pdf>
Here is one with O(m) algorithm for decrementally maintaining them: <https://arxiv.org/pdf/1901.03615.pdf> (from 2019 and it improves on the O(m\*sqrt(n)) algorithm of [https://u.cs.biu.ac.il/~liamr/scc-new.pdf](https://u.cs.biu.ac.il/%7Eliamr/scc-new.pdf))

I am not sure there is anything better for doing both operations. Part of the issue is the data structure used for maintaining them. Incremental algorithms are typically using Tarjan's Union-Find for fast partitioning of disjoint sets. While decremental algorithms are using an Even-Shiloach(ES)-tree, as the breadth-first-search representation matches the problem.

As for a unified data structure which efficiently can be used for a fully online SCC maintenance, that would be progress we hope to see soon.


---

