Fully Dynamic Transitive Closure Algorithms

Title: Fully Dynamic Transitive Closure Algorithms

Research Question: How can we efficiently maintain the transitive closure of a dynamic graph under a sequence of insertion and deletion operations?

Methodology: The researchers proposed a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. This approach allows them to improve the best known bounds for fully dynamic transitive closure. They designed a deterministic algorithm that achieves O(n2) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, their algorithm performs updates faster in O(n) amortized time.

Results: The researchers' matrix-based approach yields an algorithm for directed acyclic graphs that breaks through the O(n2) barrier on the single-operation complexity of fully dynamic transitive closure. They can answer queries in O(nǫ) time and perform updates in O(nω(1,ǫ,1)−ǫ+n1+ǫ) time, for any ǫ∈[0,1], where ω(1,ǫ,1) is the exponent of the multiplication of an n×nǫmatrix by an nǫ×nmatrix. The current best bounds on ω(1,ǫ,1) imply an O(n0.58) query time and an O(n1.58) update time. Their subquadratic algorithm is randomized, and has one-side error.

Implications: The researchers' work has significant implications for the field of dynamic graph algorithms. Their algorithms achieve subquadratic time complexity for both queries and updates, which is a major improvement over previous methods. This could lead to more efficient algorithms for maintaining transitive closure in dynamic graph applications, such as route finding in networks or querying social networks with evolving memberships.

Link to Article: https://arxiv.org/abs/0104001v1 Authors: arXiv ID: 0104001v1