Garbage collection is quite similar to view maintenance in databases (or more specifically reason maintenance / truth maintenance). Especially the fact that they found a least fix-point formulation of the problem hints at strong similarity with computing and maintaining fixpoints in deductive databases - that is computing and maintaining materialized views from some base facts and rules (a distinction that does not need to be made; base facts can be seen as special kinds of rules).

In view maintenance, there are various counting algorithms known since around 30 years - for example the PF (Propagate and Filter) algorithm, or DRed (derive-rederive) algorithm. One difference is that in garbage collection you always have the whole graph: edges and vertices, while in view maintenance you typically have only the vertices. That gives rise to the "proof traces" method of view/reason maintenance where you build up the whole graph and keep the edges even though they are useful only for maintenance (or for explanation).

The distinction of tracing garbage collection vs. reference counting garbage collection could be also seen as sort of analogous to the difference between forward chaining and backward chaining in datalog or rule systems in general.

It seems like another case where bigger awareness of results from different but related fields could help to bear fruit much faster. This paper in particular seems like something that could have been inspired by the old view maintenance research. Maybe there still are some opportunities left for transferring results from one of the fields to the other.