9
$\begingroup$

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, 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. 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!

$\endgroup$
1
$\begingroup$

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)

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.