Fully dynamic arboricity maintenance (Q5918831)

The arboricity of a graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges is defined as the minimum number of edge-disjoint forests that the edges of the graph can be partitioned into. The exact arboricity can be determined in \(O(m^{3/2}\log(n^2/m))\) time and 2-approximation in \(O(m+n)\) time. There is also an \((1+\epsilon)\)-approximation scheme that requires \(O(m\log n\log\tau \epsilon^{-1})\) time, where \(\tau\) is the arboricity of graph \(G\). This paper focuses on the dynamic graph algorithms. If edges are inserted or deleted over time, a dynamic algorithm maintains some additional graph information which is then used to calculate graph arboricity faster than a static algorithm that starts from scratch. The algorithm presented in the paper maintains a decomposition into \(\tau\) edge-disjoint spanning forests and both insertion and deletion take \(O(m\log n)\) time in the worst case. The paper concludes with an amortized bound of \(\Omega(\log n)\) for the cost of answering the arboricity query under edge insertions and deletions.