Vertex Ordering Problems in Directed Graph Streams

We consider directed graph algorithms in a streaming setting, 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 lower bounds also apply when the stream is randomly ordered: e. g. , in our most technical result we show that testing acyclicity in the p -pass random-order model requires roughly n 1+1/ p space. For other problems, random ordering can make a dramatic difference: e. g. , it is possible to find a sink in an acyclic tournament in the onepass random-order model using polylog( n ) space whereas under adversarial ordering roughly n 1/ p space is necessary and sufficient given Θ( p ) passes. 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. Together, our results complement the much maturer body of work on algorithms for undirected graph streams.

Authors

• Amit Chakrabarti
• Prantar Ghosh
• Andrew McGregor 0001
• Sofya Vorotnikova

Keywords

No keywords are indexed for this paper.