###
Incremental and Decremental Evaluation of
Transitive Closure by First-Order Queries

Guozhu Dong, The University of Melbourne

Jianwen Su,
University of California,
Santa Barbara

#### Status

in Information and Computation, pp. 101-106, 1:120, July 1995.
Preliminary results presented at the 1993
Australian Computer Science Conference.

#### Abstract

We study the following problem.
Suppose G is a graph and TCG its transitive closure.
If G' is a new graph obtained from G
by inserting or deleting an edge e,
can the new transitive closure TCG' be defined in first-order logic
using G, TCG and e?
In this paper, we show that
the answer is positive for
(1) acyclic graphs (main result),
(2) graphs where the vertices of the
deleted edge are not in the same strongly-connected component,
and
(3) graphs where there exists at most one path
between each pair of vertices (0-1-path graphs).
It is left open whether
the new transitive closure is
definable in first-order logic for all graphs.
We also consider the first-order on-line computation of the
dominator relation.