Maintaining Transitive Closure in First Order After Node-Set and Edge-Set Deletions

Document Type


Publication Date



We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graphs after the deletion of sets of edges and nodes; earlier results focused on edge-set insertions and single edge deletions. We give a generic result which asserts maintainability after deleting any “antichain” of edges. Many maintainability results follow, including after deleting any edge from acyclic graphs, after deleting any subset of all incoming (outgoing) edges to (from) any antichain family of strongly connected components (SCC), and after deleting any antichain of nodes. We then show maintainability after deleting all edges (or nodes) in any antichain family of SCCs. Finally, we show that maintainability after node deletions is at least as hard as after edge deletions.



Find in your library

Off-Campus WSU Users