The Transitive Closure of a Random Digraph

TitleThe Transitive Closure of a Random Digraph
Publication TypeTechnical Report
Year of Publication1989
AuthorsKarp, R. M.
Other Numbers546

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 $ size 9 {(*H} sup 2 n$ vertices, where $ size 9 {(*H}$ is the unique root in $[0,1]$ of the equation $1~-~x~-~e sup -cx ~=~0$. Nearly all the vertices outside the large strong component lie 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) sup 4/3 )$, where $w(n)$ is an arbitrary non-decreasing unbounded function. To circumvent the fact that the size of the transitive closure may be $(*W (n sup 2 )$ the algorithm presents the transitive closure in the compact form $(A~ times ~B)~(cu~C$, where $A$ and $B$ are sets of vertices, and $C$ is a set of arcs.

Bibliographic Notes

ICSI Technical Report TR-89-047

Abbreviated Authors

R. M. Karp

ICSI Publication Type

Technical Report