TransWikia.com

Fully dynamic algorithms for strong components of a directed graph

Theoretical Computer Science Asked by factotum on October 30, 2021

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!

One Answer

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.

Answered by Gregory Morse on October 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP