Counting edges in a DAG

In this paper we generalize a technique used by La Poutrè and van Leeuwen in for updating the "transitive closure" and the "transitive reduction" of a dag, and propose a uniform approach to deal with semi-dynamic problems on dags. We define a propagation property on a binary relationship as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem; in other words, the same procedures can be used to deal with different problems on dags by simply setting appropriate border conditions. In particular we provide semi-dynamic algorithms and data structures for maintaining a binary relationship defined over the vertices of a dag with $n$ vertices and $m$ edges, requiring O(n(q+m)) total time, for any sequence of $q$ edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Omega(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n^2). We apply the proposed technique to various problems about dominance, providing the first known incremental and decremental solutions for maintaining the "dominance relationship", the "dominator tree", and the "nearest common dominator" of a dag.