RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

ARCHIVES

On Computing
the Time Complexity
of Transitive Closure
Algorithms

Joël Coffy

Rapport de Recherche n° 10

février 1973
ON COMPUTING THE TIME COMPLEXITY OF TRANSITIVE CLOSURE ALGORITHMS

Joël Coffy

(présenté par J.M. Cadiou)

Abstract

Two different algorithms to compute the transitive closure of a directed
graph have been presented by WARSHALL & PURDOM, in the chronological order.
PURDOM establishes also that for graphs selected at random with equal probabili-
ty among those which satisfy a given hypothesis P, the time complexity t(n)
of WARSHALL's algorithm satisfies :

$$
\lim_{n \to \infty} \frac{n^2}{t(n)} = 0 \qquad (1)
$$

where n is the number of vertices of the graph.

The purpose of this note is to prove that the hypothesis P above is
satisfied by all graphs, thus establishing the generality of (1).
# 1. Introduction

In [4,5], PURDOM presents an algorithm for computing the transitive closure of a directed graph G, and compares it with the well-known algorithm of WARSHALL [6].

PURDOM establishes that for graphs selected at random with equal probability among those which satisfy HYPOTHESIS P below, the time complexity $t(n)$ (number of Boolean operations) necessary to compute the transitive closure by WARSHALL's algorithm, satisfies

$$ \lim_{n \to \infty} \frac{n^2}{t(n)} = 0 \quad (1) $$

where n is the number of vertices of the graph. Although PURDOM [4] conjectures that HYPOTHESIS P is satisfied by all graphs, he is unable to provide a proof.

The purpose of this note is to prove that HYPOTHESIS P is satisfied by all graphs, thus establishing the generality of (1).

# HYPOTHESIS P.

In a directed graph G :

$$ N_k \ge \frac{k}{\sqrt{2}} \sqrt{N_t} \quad (2) $$

where :

- $k$ is an integer, with $0 \le k \le \sqrt{2N_t}$.

- $N_k$ is the number of ordered pairs of vertices connected by a path of length $k$ or less in G.

- $N_t$ is the number of arcs in the transitive closure of G.

# 2. Preliminaries.

If the directed graph G in (2) has n vertices numbered from 1 to n, its adjacency matrix A is an nxn matrix whose entries $a_{ij}$ are defined by : $a_{ij} = 1$ if there is an arc from vertex i to vertex j, $a_{ij} = 0$ otherwise, for $1 \le i, j \le n$. (See [2] p 202). Then $N_k$ and $N_t$ of hypothesis P are equal to the number of non zero entries in the matrices :
$k$ 
$\sum_{i=1}^{k} A_i^i$ and $\sum_{i=1}^{\infty} A_i^i = \sum_{i=1}^{\infty} A_i^i$, respectively.

To prove (P) we will modify inequality (2). More precisely, let L be the
maximal length of a path in G (where all vertices are distinct, with the possi-
ble exception of the first and the last one). Then :

To prove (P) we will modify inequality (2). More precisely, let L be the
maximal length of a path in G (where all vertices are distinct, with the possi-
ble exception of the first and the last one). Then :

**Lemma 1 :**

$$
L \le \sqrt{2N_t}
$$

Proof : let $x_1, \dots, x_{L(L+1)}$ be such a path ; it constitutes a subgraph G'
of G for which $N' = \frac{L(L+1)}{2}$ if $x_{L+1} \ne x_1$ and $N' = L^2$ for $x_{L+1} = x_1$. In both
cases $L \le \sqrt{2N'}_t \le \sqrt{2N_t}$. ■

<figure><img src="image_1.png" /><figcaption>Figure 1.</figcaption></figure>

P implies that the curve $N_k = N(k)$ lies above the line $D : y = k \sqrt{\frac{N_t}{2}}$
for $k \in [0, \sqrt{2N_t}]$. (See figure 1). Lemma 1 and the fact that $N_k = N_t$ for $k \ge L$
imply that (P) is equivalent to theorem (P') where :

**Theorem (P') :**

$$
N_k \ge \frac{k}{\sqrt{2}} \sqrt{N_t} \text{ for } 1 \le k \le L.
$$

The remainder of this note is devoted to the proof of (P').

**Remark :**

If (P') is true for G, it is also true for the graph G' obtained by
adding a loops to G (a loop is an arc whose initial and terminal vertices
coincide).
Indeed we have two cases : either these loops correspond to diagonal entries of Σ Aᵢᵢ which are equal to 1, and then in (P') only the left hand side increases, or they correspond to diagonal entries of (Σ Aᵢᵢ) which are zero and then one has to check :

$$2(N_k + \alpha)^2 \geq k^2 (N_t + \alpha) \quad (3)$$

for $1 \leq k \leq L$

where L is the same for G and G'. But (3) is true because

$$2N_k^2 \geq k^2 N_t \quad \text{and} \quad N_k \geq \frac{k(k+1)}{2}.$$

Thus, it is sufficient to prove (P') for graphs without loops.

### 3. Proof of (P').

The proof of (P') will essentially proceed by an induction on the decomposition of G into strongly connected components. Let us first recall some standard definitions and results about graphs (see for example [2] p 200).

Let G be a directed graph :

(a) G is said to be **strongly connected** iff for every pair of vertices x,y in G there is a path from x to y and a path from y to x.

(b) every graph G can be uniquely decomposed into maximal strongly connected subgraphs, called its **strongly connected components**. We will denote them G₁, G₂, ..., Gₚ.

(c) The condensation graph of G, denoted Gₓ, is the graph whose vertices are the strongly connected components G₁, G₂, ..., Gₚ of G and which has an arc from Gᵢ to Gⱼ iff there is an arc from some vertex of Gᵢ to some vertex of Gⱼ in G. It is clear that Gₓ has no circuit, which means that its adjacency matrix can be made upper triangular by properly reordering its vertices.

(d) This means in turn that the adjacency matrix A of G can be made upper block triangular, as shown in fig 2.
<figure><img src="image_2.png" /><figcaption>Figure 2.</figcaption></figure>

Each of the blocks on the diagonal is the adjacency matrix of one of the strongly connected components of G. (If one of these components is reduced to a single vertex, the corresponding block in the matrix A is reduced to a zero entry on the diagonal, since G has no loops).

(e) Let us denote C the component of G which corresponds to the lower right block on the diagonal. Then every arc of G originating in C terminates in C.

(f) If $G_1, G_2$ are two directed graphs with disjoint sets of vertices $S_1$ and $S_2$, we define :

- $G_1UG_2$, the union of $G_1$ and $G_2$ as the graph whose set of vertices S is $S_1US_2$ and whose arcs are those of $G_1$ and $G_2$. The corresponding adjacency matrix is as shown in Fig 3 :

<figure><img src="image_3.png" /><figcaption>Figure 3.</figcaption></figure>
- $G_1 \to G_2$ any graph whose set of vertices $S$ is $S_1 \cup S_2$ and whose arcs include those of $G_1$ and $G_2$, as well as some arcs connecting vertices of $G_1$ to vertices of $G_2$. The corresponding adjacency matrices are as shown in Fig 4 :

<figure><img src="image_4.png" /><figcaption>Figure 4.</figcaption></figure>

Then :

**Lemma 2 :**

Every finite graph $G$ either is strongly connected or is of the form $G'UC$ or $G' \to C$ where $C$ is strongly connected and $G'$ has strictly less vertices than $G$.

**Proof :**

The three cases correspond respectively to the conditions

$$C = A, C_1 = 0, C_1 \neq 0 \text{ in fig 2.} \square$$

As announced previously, we will now prove (P') by induction on the decomposition of $G$ provided by Lemma 2. More precisely :

- we first verify (P') for strongly connected graphs (Lemma 3).

- then we assume (P') true for an arbitrary graph $G$, and prove that, for every strongly connected graph $C$, (P') is true for $GUC(\text{Lemma 4})$ and $G \to C$ (Lemma 5).

**Definition**

Let $x, y$ be two vertices of a directed graph $G$. We denote $d(x,y)$, the *distance* from $x$ to $y$, the length of the shortest path from $x$ to $y$ in $G$. Equiva- lently, we say that $y$ is at distance $d(x,y)$ of $x$. If there is no path from $x$ to $y$, we say that $d(x,y) = \infty$.
**Lemma 3 :**

Let $C$ be a strongly connected graph, and $i$ an arbitrary vertex of $C$.
Let $n_{ki}$ denote the number of vertices $j$ of $C$ such that $d(i,j) \le k$. Then :

$$ \forall i, 1 \le i \le n, n_{ki} \ge k \quad (4) $$

$$ \text{Hence : } N_k \ge kn. \quad (5) $$

**Proof :** each vertex $i$ of the graph is the root of a spanning tree of $C$.
(See [3], ex 13, p 277). $\square$

Notice that for a strongly connected graph one gets an inequality (5)
stronger than (P'), since $N_t = n^2$.

**Lemma 4 :**

Let $G_1, G_2$ be two directed graphs. If (P') is true for $G_1$ and $G_2$, it is
true for $G_1 \cup G_2$.

**Proof :** Let $N_{ki}, N_{ti}, L_i$, be the variables corresponding to $G(i=1,2)$,
as introduced in § 1 and 2. For $k \le \min(L_1, L_2)$, SCHWARZ's inequality gives the
result. For $\min(L_1, L_2) \le k \le \max(L_1, L_2)$, (assume for example $L_1 \le k \le L_2$) one
gets the result by observing that $N_{k2} \ge \frac{k}{2}$. $\square$

Finally :

**Lemma 5 :**

If (P') is true for (G), it is true for $G' = G \stackrel{\rightarrow}{\rightarrow} C$.

**Proof :** Let $X_k$ be the set of vertices of $G$ at distance $k$ of $C$ (the
distance of a point $x$ of $G$ to $C$ is by definition $\min\{d(x,y)|y\in C\}$), and
$n_k = |X_k|$. The $X_k$'s are disjoint and $I_k = \sum_{l=1}^k n_l$ is the cardinal of the set of
vertices of $G$ at a distance less than or equal to $k$ of $C$. By hypothesis
$n_l \ne 0$. Let $N_k, N_t, L$ and $N'_k, N'_t, L'$ be the variables corresponding to $G$
and $G'$. Let $v$ be the maximal value of $k$ such that $n_k \ne 0$. We have : $v \le L+1$.
Let $M_k$ (respectively $P_k$) be the cardinality of set of pairs

$$ \{(x,y) | x \in G, y \in C, d(x,y) \le k\} $$

(respectively $\{(x,y) | x \in C, y \in C, d(x,y) \le k\}$).

One has :

$$ N'_{k} = N_{k} + M_{k} + P_{k} \quad (6) $$

$$ \text{and } N'_{t} = N_{t} + I_{c} + c^{2} \quad (7) $$

where $I = I_v$.
Bounds on the variables $N_k$, $M_k$, $P_k$, will be computed as functions of the $n_j$'s and of $|C|$. Different cases will appear according to the relative values of $k, L, v, c = |C|$.

(P') can now be written :

$$2(N_k + M_k + P_k)^2 \geq k^2 (N_t + c(I + c)) \quad (7 \text{ bis})$$

we have two main cases :

### Case I : $v+c-1 \leq k$

This means that two points of $G'$ at distance $k$ belong to $G$; hence $k \leq L$. We then have :

$$P_k = c^2 \quad (8)$$

$$M_k = cI^2 \quad (9)$$

$$N_k \geq \frac{k}{2} \quad (10)$$

because there is in $G$ a path of length less than or equal to $k$. since $k \leq L$.

$$2N_k^2 \geq k^2 N_t \quad (11)$$

by the induction hypothesis.

By (11), (7 bis) is implied by :

$$2(M_k + P_k)(2N_k + M_k + P_k) \geq k^2 c(I + c) \quad (12)$$

By (8,9,10), the left member is larger than :

$$2(cI + c^2)(k^2) = 2k^2 c(I + c), \text{ and so}$$

Case I is proved.

### Case II : $k \leq v+c-1$.

In this case one checks the following inequalities :

$$\left\{ \begin{array}{l} M_k + P_k \geq k c \\ 2N_k (N_k + M_k + P_k) \geq k^2 N_t \end{array} \right. \quad (13)$$

$$2N_k (N_k + M_k + P_k) \geq k^2 N_t \quad (14)$$

To prove the above inequalities, we first establish :

$$N_k \geq \inf_{i \geq 1} (i - 1, k) n_i \quad (15)$$

$$M_k \geq \inf_{1 \leq i \leq k} (c, k - i + 1) n_i \quad (16)$$

(with the understanding that, for $i \geq v$, $n_i = 0$)

$$\text{and for } k \leq c, \quad \left\{ \begin{array}{l} P_k \geq k c \\ M_k + N_k \geq kI \end{array} \right. \quad (17)$$

$$M_k + N_k \geq kI \quad (18)$$

$$\text{for } k \geq c, \quad P_k = c^2 \quad (19)$$
## Proof of (15,16,17,18,19)

(15) expresses the fact that every point of X is at a distance (i-j) of at least one point of X (for i > j).

(16) expresses the fact that every point of X is at a distance less than or equal to k, of at least (k-i+1) points of C, or of c points of C if $c \le (k-i+1)$.

(17) and (19) are just Lemma 3.

(18) is a consequence of (15,16).

We now have :

### Sublemma A : proof of (13), i.e. of $M_k + P_k \ge kc$

$$a) \underline{k \ge c}$$

$$ 
\begin{align*}
P_k &= c^2 \\
M_k &\ge cn_1 + cn_2 + \dots + cn_{k-c+1} + (c-1)n_{k-c+2} + \dots + n_k \\
    &\ge (k-c+1)c, \text{ since } k \le (v+c-1) \text{ implies } k-c+1 \le v \\
\text{and} \quad n_i &\ge 1 \text{ for } 1 \le i \le v, \\
\text{finally} \quad M_k + P_k &\ge (k-c+1)+c^2 \ge kc.
\end{align*}
$$

$$b) \underline{k \le c}$$

$$P_k \le kc, \text{ hence : } M_k + P_k \ge kc.$$

### Sublemma B : proof of (14) i.e. $2N_k(N_k + M_k + P_k) \ge k^2 N_t$

$$a) \underline{k \le \sqrt{2N_t}}$$

by the induction hypothesis $2N_k^2 \ge k^2 N_t$.

$$b) \underline{k \ge \sqrt{2N_t}}$$

$N_k = N_t$. G' contains a path of length larger than or equal to k and $N'_k = N_k + M_k + P_k \ge \frac{k^2}{2}$.

We now have two subcases :

$$\text{II, a) } \underline{k \le c}$$

We have :

$$P_k \ge kc \qquad (20)$$
(13,18,20) prove the following :

$$2(M_k + P_k)(M_k + N_k + P_k) \geq 2kc(kI + kc) \quad (21)$$

(14,21) establish (7 bis) in this case.

$II, \beta) \ k \geq c+1$

We have :

$$M_k \geq \sum_{i=1}^{k} \inf(c, k-i+1) n_i = c \sum_{1}^{k-c} n_i + \sum_{k-c+1}^{k} (k-i+1) n_i \quad (22)$$

(with the understanding that $n_i = 0$ for $i \ge v$).

From (15,22) we have :

$$M_k + N_k \geq \sum_{1}^{k-c} (c+i-1)n_i + \sum_{k-c+1}^{v} k \sum_{1}^{k} n_i \quad (23)$$

By (14), (7bis) is implied by :

$$2(M_k + P_k) \left( \sum_{1}^{k-c} (c+i-1)n_i + k \sum_{k-c+1}^{v} n_i + 2c^2 \right) \geq k^2 c \left( \sum_{1}^{k-c} n_i + \sum_{k-c+1}^{v} n_i \right) \quad (24)$$

Since $M_k + P_k \ge kc$, we can get rid of the terms $\sum_{k-c+1}^{v} n_i$ and (24) is implied by :

$$(M_k + P_k) \left( 2 \sum_{1}^{k-c} (c+i-1)n_i - 1 \right) n_i + k \sum_{k-c+1}^{v} n_i + 2c^2 \geq k^2 c \left( \sum_{1}^{k-c} n_i + c \right) \quad (25)$$

The second parenthesis on the left is larger than $k^2$; indeed it is larger than :

$$(k-c)(k-c+1)+2c(k-c)+k(v+c-k)+2c^2 \\ = k(v+c-1)+c(c+1) \geq k^2 + c(c+1) \\ \qquad k-c$$

but $M_k + P_k \ge c \left( \sum n_i + c \right)$ and (25) is proved. Lemma 5 is verified.

The five lemmas establish the proof of (P'), hence of (P). □

Let us close with a

### REMARK.

One might think of a simpler proof of conjecture (P') by first trying to prove that the curve $N_k = N(k)$ is convex on the interval $[0, \sqrt{2N_k}]$; unfortunately this fails; $N(k)$ is not convex for the graph of fig 5 for example (for this graph, $N(k)$ is shown in fig 6).
<figure><img src="image_5.png" /><figcaption>Figure 5.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 6.</figcaption></figure>

The author acknowledges helpful discussions with J.M. CADIOU.
References

[1] BERGE Claude, Theorie des graphes et ses applications, Dunod 1967.

[2] HARARY Franck, Graph theory, 1969, Addison Wesley.

[3] KNUTH Donald, The art of computer programming, vol 1, Addison Wesley, 1968.

[4] PURDOM Paul, A transitive closure algorithm, Computer Science Technical Report # 33, 1968, University of Wisconsin.

[5] PURDOM Paul, A transitive closure algorithm, BIT 10, 1970, p76-94.

[6] WARSHALL Stephen, A theorem on boolean matrices, JACM 9, (1962) 11-12.