{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih7fih4xyfbgwvbw373uvcl5lfh6cyq2m44ur2wlf63xjgz4jsvua",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mlcv6drfj5b2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.06555v1",
  "publishedAt": "2026-05-08T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Benjamin Aram Berendsohn",
    "Marek Sokołowski"
  ],
  "textContent": "**Authors:** Benjamin Aram Berendsohn, Marek Sokołowski\n\nWe study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size $n$ under edge deletions, weight updates, and a certain information-retrieval query. Both problems can be solved in $O(\\log n)$ time per update/query using standard dynamic forest data structures like top trees, even if additionally edge insertions are allowed. We investigate whether the deletion-only problem can be solved faster. First, we consider $\\texttt{tree-sum}$ queries, where we ask for the sum of vertex weights in one of the connected components (i.e., trees) in the forest. We give a data structure with $O(n)$ preprocessing time and $O(\\log^* n)$ time per operation, based on a micro-macro tree decomposition (Alstrup et al., 1997). If the forest is unweighted (i.e., all weights are 1 and cannot be changed), then the operation time can be improved to $O(1)$. Additionally, we give an asymptotically universally optimal algorithm. More specifically, our algorithm works in the group model, and processes $m$ operations on an initial forest $F$ in running time $O( \\mathrm{OPT}(F, m) )$. Here $\\mathrm{OPT}(F, m)$ is the number of weight additions and subtractions that a best possible algorithm performs to handle a worst-case instance for a fixed initial forest $F$ and a fixed number $m$ of operations. We achieve this with a combination of the aforementioned decomposition technique, precomputation of optimal data structures for very small instances, and some insights into the behavior of $\\mathrm{OPT}$. Note that even the worst-case complexity of this algorithm remains unknown to us. Second, we consider $\\texttt{subtree-sum}$ queries. Here, the forest is rooted, and a query $\\texttt{subtree-sum}(v)$ returns the sum of weights in the subtree rooted at $v$. We show tight bounds for several variants of this problem. [...]",
  "title": "Fast decremental tree sums in forests"
}