External-Memory Breadth-First Search with Sublinear I/O

Breadth-first search (BFS) is a basic graph exploration technique. We give the first external-memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires O( n + sort(n+m) ) I/Os on a graph with n nodes and m edges and a machine with main-memory of size M, D parallel disks, and block size B. We present two versions of a new algorithm which requires only O( sqrt( n/m * (n+m)/(D*B) ) * log_{M/B} (n/B) + sort(n+m)) I/Os (expected or worst-case, respectively). Hence, for m = O(n), they improve upon the I/O-performance of the best previous algorithm by nearly a factor of sqrt(D*B). Our approach is fairly simple and we conjecture at least the randomized version to be practical