# Vertex Ordering Problems in Directed Graph Streams

arXiv: https://arxiv.org/abs/2105.08215 · HTML: https://mlsanity.com/paper/2105.08215/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2021.

## Built on by (most cited first, 1 of 1)

- [Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2412.16181/) (2024)

## Abstract (arXiv)

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 n1+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 one-pass random-order model using polylog(n) space whereas under adversarial ordering roughly n1/p space is necessary and sufficient given Theta(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.