MAINTAINING TRANSITIVE CLOSURE IN FIRST-ORDER AFTER NODE-SET AND EDGE-SET DELETIONS

We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graph s after the deletion of sets of edges and nodes; earlier results focus ed 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 deleti ng any edge from acyclic graphs, after deleting any subset of all inco ming (outgoing) edges to (from) any antichain family of strongly conne cted components (SCC), and after deleting any antichain of nodes. We t hen shaw maintainability after deleting all edges (or nodes) in any an tichain family of SCCs. Finally, we show that maintainability after no de deletions is at least as hard as after edge deletions. (C) 1997 Els evier Science B.V.