25-1 Transitive closure of a dynamic graph

Suppose that we wish to maintain the transitive closure of a directed graph $G = (V, E)$ as we insert edges into $E$. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph $G$ has no edges initially and that we represent the transitive closure as a boolean matrix.

a. Show how to update the transitive closure $G^* = (V, E^*)$ of a graph $G = (V, E)$ in $O(V^2)$ time when a new edge is added to $G$.

b. Give an example of a graph $G$ and an edge $e$ such that $\Omega(V^2)$ time is required to update the transitive closure after the insertion of $e$ into $G$, no matter what algorithm is used.

c. Describe an efficient algorithm for updating the transitive closure as edges are inserted into the graph. For any sequence of $n$ insertions, your algorithm should run in total time $\sum_{i = 1}^n t_i = O(V^3)$, where $t_i$ is the time to update the transitive closure upon inserting the $i$th edge. Prove that your algorithm attains this time bound.

a. Let $T = (t_{ij})$ be the $|V| \times |V|$ matrix representing the transitive closure, such that $t_{ij}$ is $1$ if there is a path from $i$ to $j$, and $0$ otherwise.

Initialize $T$ (when there are no edge in $G$) as follows:

$$ t_{ij} = \begin{cases} 1 & \text{if $i = j$}, \\ 0 & \text{otherwise}. \end{cases} $$

We update $T$ as follows when an edge $(u, v)$ is added to $G$:

1
2
3
4
5
6
TRANSITIVE-CLOSURE-UPDATE(T, u, v)
    let T be |V| × |V|
    for i = 1 to |V|
        for j = 1 to |V|
            if t[i, u] == 1 and t[v, j] == 1
                t[i, j] = 1
  • With this procedure, the effect of adding edge $(u, v)$ is to create a path (via the new edge) from every vertex that could already reach $u$ to every vertex that could already be reached from $v$.
  • Note that the procedure sets $t_{uv} = 1$, because both $t_{uu}$ and $t_{vv}$ are initialized to $1$.
  • This procedure takes $\Theta(V^2)$ time because of the two nested loops.

b. Consider inserting the edge $(v_{|V|}, v_1)$ into the straight-line graph $v_1 \to v_2 \to \cdots \to v_{|V|}$.

Before this edge is inserted, only $|V|(|V| + 1) / 2$ entries in $T$ are $1$ (the entries on and above the main diagonal). After the edge is inserted, the graph is a cycle in which every vertex can reach every other vertex, so all $|V|^2$ entries in $T$ are $1$. Hence $|V|^2 - (|V|(|V| + 2) / 2) = \Theta(V^2)$ entries must be changed in $T$, so any algorithm to update the transitive closure must take $\Omega(V^2)$ time on this graph.

c. The algorithm in part (a) would take $\Theta(V^4)$ time to insert all possible $\Theta(V^2)$ edges, so we need a more efficient algorithm in order for any sequence of insertions to take only $O(V^3)$ total time.

To improve the algorithm, notice that the loop over $j$ is pointless when $t_{iv} = 1$. That is, if there is already a path $i \leadsto v$, then adding the edge $(u, v)$ cannot make any new vertices reachable from $i$. The loop to set $t_{ij}$ to $1$ for $j$ such that there exists a path $v \leadsto j$ is just setting entries that are already $1$. Eliminate this redundant processing as follows:

1
2
3
4
5
6
7
TRANSITIVE-CLOSURE-UPDATE(T, u, v)
    let T be |V| × |V|
    for i = 1 to |V|
        if t[i, u] == 1 and t[i, v] == 0
            for j = 1 to |V|
                if t[v, j] == 1
                    t[i, j] = 1

We show that this procedure takes $O(V^3)$ time to update the transitive closure for any sequence of $n$ insertions:

  • There cannot be more than $|V|^2$ edges in $G$, so $n \le |V|^2$.
  • Summed over $n$ insertions, the time for the outer for loop header and the test for $t_{iu} == 1$ and $t_{iv} == 0$ is $O(nV) = O(V^3)$.
  • The last three lines, which take $O(V^2)$ time, are executed only $O(V^2)$ times for $n$ insertions. To see why, notice that the last three lines are executed only when $t_{iv}$ equals $0$, and in that case, the last line sets $t_{iv} = 1$. Thus, the number of $0$ entries in $T$ is reduced by at least $1$ each time the last three lines run. Since there are only $|V|^2$ entries in $T$, these lines can run at most $|V|^2$ times.
  • Hence, the total running time over $n$ insertions is $O(V^3)$.