Estimating the size of the transitive closure in linear time

Computing transitive closure and reachability information in directed graphs is a fundamental graph problem with many applications. The fastest known algorithms run in O(sm) time for computing all nodes reachable from each of 1⩽s⩽n source nodes, or, using fast matrix multiplication, in O(n^2.38) time for computing the transitive closure, where n is the number of nodes and m the number of edges in the graph. In query optimization in database applications it is often the case that only estimates on the size of the transitive closure and on the number of nodes reachable from certain nodes are needed. We present an O(m) time randomized algorithm that estimates the number of nodes reachable from every node and the size of the transitive closure. We also obtain a O˜(m) time algorithm for estimating sizes of neighborhoods in directed graphs with nonnegative weights, avoiding the O˜(mn) time bound of explicitly computing these neighborhoods. Our size-estimation algorithms are much faster than performing the actual computations and improve significantly over previous estimation methods