The transitive closure of a random digraph

Abstract

Abstract In a random n ‐vertex digraph, each arc is present with probability p , independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when n is large and np is equal to a constant c greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ 2 n vertices, where Θ is the unique root in [0, 1] of the equation 1 − x − e −ex = 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time O(n). for all choices of n and p , the expected execution time of the algorithm is O(w(n) ( n log n ) 4/3 ), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω( n 2 ) the algorithm presents the transitive closure in the compact form (A × B) U C , where A and B are sets of vertices, and C is a set of arcs.