Vertex Ordering Problems in Directed Graph Streams

Most of the literature on graph streaming algorithms considers only undirected graphs. In this talk I will present some very recent results on digraph streaming, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sorting and acyclicity testing. We also study the related problems of finding a minimum feedback arc set (edges whose removal yields an acyclic graph), and finding a sink vertex. We are interested in both adversarially-ordered and randomly-ordered streams. For arbitrary input graphs with edges ordered adversarially, we show that most of these problems have high space complexity, precluding sublinear-space solutions. Some (weaker) lower bounds also apply when the stream is randomly ordered: e.g., testing acyclicity in the p-pass random-order model requires roughly n^{1+1/p} space. For sink-finding, we show that while a p-pass solution requires about n^{1/p} space under adversarial ordering, this improves dramatically to poly(log n) space in a single pass under random ordering. We also design sublinear algorithms for the feedback arc set problem in tournament graphs; for random graphs; and for randomly ordered streams. In some cases, we give lower bounds establishing that our algorithms are essentially space-optimal. This talk is based on joint worth with Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova and was begun during my visit to Simons for the Foundations of Data Science program.