I have an infinite set of possible nodes $V$ and a "root node" $r \in V$. I would like to maintain a directed graph with the invariant that all nodes in the graph are reachable from $r$. That is, the graph starts with a set of nodes $\{r\} \subset V$ and arcs $\varnothing \subset V^2$, and the allowed operations are as follows:
- Query the number of nodes reachable from $r$.
- Create an arc from a node $u$ in the graph to a node $v$ not in the graph (if it helps, you can assume that $v$ has never been in the graph), adding $v$ to the graph in the process.
- Create an arc from a node $u$ in the graph to a node $v$ also in the graph.
- Delete an arc $(u, v)$ from the graph, in the process deleting all nodes and arcs now unreachable from $r$ (or, equivalently, doing nothing else, as long as the assumption on (2) holds about new nodes never having previously been in the graph, and if (1) can still be implemented efficiently).
An ideal solution would be constant-time for (1), (2), and (3); and for (4), the time complexity would be proportional to the number of nodes deleted. It is trivial to implement a data structure that is constant-time for (1), (2), and (3) with time complexity of (4) proportional to the number of all nodes in the graph at the time; I do not consider that a successful solution for this theoretical question.
I found Alexander Svozil's 2018 answer about dynamic connectivity, which cites (among others) this paper:
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time - Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen -https://arxiv.org/abs/1901.03615 - accepted at STOC 2019
This seems close to what I want, but it's only decremental and not fully dynamic as my setting is here. The cited papers about the fully dynamic setting seem to be just theoretical lower bounds and not actual algorithms; does this mean that this data structure cannot be made efficient? Crucially, though, my setting is slightly different from that framing of fully dynamic strongly connected-components and single-source reachability: in that problem, an arc could be deleted which affects reachability of many nodes, and then immediately re-added to make all those nodes reachable again. In my setting, those nodes are gone, and any new arcs must build up gradually rather than making many nodes reachable all at once. This seems to suggest to me that my setting could possibly be more similar to the decremental setting than the fully dynamic one, but I don't understand the details here nearly well enough to tell whether that's the case; hence my question.
For context, this is just a simplified version of the problem of garbage collection (GC): dynamically allocate/modify/deallocate objects that may point to other objects, and continuously free memory used by objects that become unreachable. I understand that garbage collection is a well-studied topic, but I'm having trouble finding the answer to my specific theoretical question here. For instance, Wikipedia describes the two most common GC strategies:
- Tracing implements arc deletion by periodically doing graph search from $r$, then deleting all nodes not found by the search. This visits all nodes in the graph, not just the deleted ones, so it seems that it could revisit many nodes over and over while not deleting them. This is similar the "trivial" solution I mentioned above, which I do not consider sufficiently performant (in a theoretical sense, not a practical sense).
- Reference counting doesn't fully solve this problem in the presence of cycles.
Thus, my question is: How can I efficiently implement this dynamic graph data structure? Or, where can I find a rigorous argument that it is not possible?
