Half-Approximating Maximum Dicut in the Streaming Setting

We study streaming algorithms for the maximum directed cut problem. The edges of an n-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With O(n) space, a (1 -ε)-approximation can be trivially obtained for any fixed ε > 0 using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., n 1-Ω(1) ) space.

A lower bound of Kapralov and Krachun (STOC'19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS'23). The same authors later obtained a (1/2 -ε)-approximation, assuming that the graph is constant-degree (SODA'25).

In this paper, we show that for any ε > 0, a (1/2 -ε)-approximation of maximum dicut value can be obtained with n 1-Ωε(1) space in general graphs. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high-and low-degree vertices, when simulating a suitable local algorithm.

Independent work: An independent and concurrent work of Velusamy [30] gives a (1/2 -ε)approximation of max dicut in n 1-Ωε(1) space and two passes. Our algorithm has the same approximation/space trade-off but runs in a single pass instead of two.