INCREMENTAL AND DECREMENTAL EVALUATION OF TRANSITIVE CLOSURE BY FIRST-ORDER QUERIES

We study the following problem. Suppose G is a graph and TCG its trans itive closure. If G' is a new graph obtained from G by inserting or de leting an edge e, can the new transitive closure TCG, be defined in fi rst-order logic using G, TCG and e? In this paper, we show that the an swer is positive for (1) acyclic graphs (main result), (2) graphs wher e the vertices of the deleted edge are not in the same strongly connec ted component, and (3) graphs where there exists at most one path betw een each pair of vertices (0-1-path graphs). It is left open whether t he new transitive closure is definable in first-order logic for all gr aphs. We also consider the first-order on-line computation of the domi nator relation. (C) 1995 Academic Press, Inc.