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. We can update the transitive closure in time $O(V^2)$ as follows. Suppose that we add the edge $(x_1, x_2)$. Then, we will consider every pair of vertices $(u, v)$. In order to of created a path between them, we would need some part of that path that goes from $u$ to $x_1$ and some second part of that path that goes from $x_2$ to $v$. This means that we add the edge $(u, v)$ to the transitive closure if and only if the transitive closure contains the edges $(u, x_1)$ and $(x_2, v)$. Since we only had to consider every pair of vertices once, the runtime of this update is only $O(V^2)$.

b. Suppose that we currently have two strongly connected components, each of size $|V| / 2$ with no edges between them. Then their transitive closures computed so far will consist of two complete directed graphs on $|V| / 2$ vertices each. So, there will be a total of $|V|^2 / 2$ edges adding the number of edges in each together. Then, we add a single edge from one component to the other. This will mean that every vertex in the component the edge is coming from will have an edge going to every vertex in the component that the edge is going to. So, the total number of edges after this operation will be $|V| / 2 + |V| / 4$ So, the number of edges increased by $|V| / 4$. Since each time we add an edge, we need to use at least constant time, since there is no cheap way to add many edges at once, the total amount of time needed is $\Omega(|V|^2)$.

c. We will have each vertex maintain a tree of vertices that have a path to it and a tree of vertices that it has a path to. The second of which is the transitive closure at each step. Then, upon inserting an edge, $(u, v)$, we will look at successive ancestors of $u$, and add $v$ to their successor tree, just past $u$. If we ever don't insert an edge when doing this, we can stop exploring that branch of the ancestor tree. Similarly, we keep doing this for all of the ancestors of $v$. Since we are able to short circuit if we ever notice that we have already added an edge, we know that we will only ever reconsider the same edge at most $n$ times, and, since the number of edges is $O(n^2)$, the total runtime is $O(n^3)$.