Streaming beyond sketching for Maximum Directed Cut
share
We give an O(√(n))-space single-pass 0.483-approximation streaming algorithm for estimating the maximum directed cut size () in a directed graph on n vertices. This improves over an O(log n)-space 4/9 < 0.45 approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for o(√(n))-space algorithms. is a special case of a constraint satisfaction problem (CSP). In this broader context, our work gives the first CSP for which algorithms with O(√(n)) space can provably outperform o(√(n))-space algorithms on general instances. Previously, this was shown in the restricted case of bounded-degree graphs in a previous work of the authors (SODA 2023). Prior to that work, the only algorithms for any CSP were based on generalizations of the O(log n)-space algorithm for , and were in particular so-called "sketching" algorithms. In this work, we demonstrate that more sophisticated streaming algorithms can outperform these algorithms even on general instances. Our algorithm constructs a "snapshot" of the graph and then applies a result of Feige and Jozeph (Algorithmica, 2015) to approximately estimate the value from this snapshot. Constructing this snapshot is easy for bounded-degree graphs and the main contribution of our work is to construct this snapshot in the general setting. This involves some delicate sampling methods as well as a host of "continuity" results on the behaviour in graphs.
READ FULL TEXT