A uniform approach to semi-dynamic problems on digraphs

In this paper we propose a uniform approach to deal with incremental problems on digraphs and with decremental problems on dags generalizing a technique used by La Poutre and van Leeuwen in [17] for updating the transitive closure and the transitive reduction of a dag. We define a propagation property on a binary relationship over the vertices of a digraph 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 by simply setting appropriate boundary conditions. In particular, we provide semi-dynamic algorithms and data structures for maintaining a binary relationship over the vertices of a digraph (dag) with n vertices and m edges, requiring O(n max {q, m}) total time for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Ω(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n2). We apply the proposed technique to various problems about dominance, providing a solution to the problems of maintaining the dominance relationship, the dominator tree, and the nearest common dominator of a digraph in the incremental case, and of a dag in the decremental case; no dynamic solution was previously known for some of these problems. Finally we mention that the algorithms indeed work correctly also for interleaved sequences of insertion and deletion of edges in a dag, although the complexity bound holds for monotone sequence of updates only.