The best approximation ratio for maximum directed cut

Maximum directed cut asks for a set of vertices that maximizes the total weight of arcs leaving it. Assuming the Unique Games Conjecture, the best ratio a polynomial-time algorithm can guarantee is now known to lie between 0.87446 and 0.87461, and the question is what the exact value is.

Problem

Let $G=(V,E)$ be a directed graph with nonnegative arc weights $w$. For $S \subseteq V$ let $\delta^+(S)$ be the set of arcs $(u,v)\in E$ with $u \in S$ and $v \notin S$, and let

$$\mathrm{OPT}(G) = \max_{S \subseteq V} w\big(\delta^+(S)\big).$$

A randomized polynomial-time algorithm is an $\alpha$-approximation for MAX DI-CUT if on every instance it outputs a set $S$ with $\mathbb{E}\,[w(\delta^+(S))] \ge \alpha \cdot \mathrm{OPT}(G)$. Equivalently, MAX DI-CUT is the constraint satisfaction problem whose constraints have the form $\bar x_u \wedge x_v$ on Boolean variables. Let $\alpha_{\text{DI-CUT}}$ be the best ratio achievable in polynomial time, assuming the Unique Games Conjecture (UGC).

Question. Determine $\alpha_{\text{DI-CUT}}$. It is known that $0.87446 \le \alpha_{\text{DI-CUT}} \le 0.87461$.

Background

Goemans and Williamson's semidefinite programming method (1995) gives a ratio $\alpha_{\text{GW}} \approx 0.87856$ for undirected MAX CUT, and Khot, Kindler, Mossel and O'Donnell showed that, under UGC, nothing better is possible [4, 5]. Feige and Goemans, who improved the algorithms for the directed version [3], asked whether it can be approximated as well as MAX CUT [1]. Raghavendra's theorem says that under UGC a canonical SDP with the right rounding is optimal for every such problem, but it gives no practical way to compute the resulting number, so the exact ratio for MAX DI-CUT is still unknown. The question was posted on TCS Open Problems in 2026.

What is known

• Upper bound. Assuming UGC, $\alpha_{\text{DI-CUT}} \le 0.87461$ (Brakensiek, Huang, Potechin and Zwick, 2023) [1]. Since this is below $\alpha_{\text{GW}}$, MAX DI-CUT is strictly harder to approximate than MAX CUT, which answers Feige and Goemans's question. The proof is analytical, and the authors expect more elaborate constructions to lower it slightly.
• Lower bound. $\alpha_{\text{DI-CUT}} \ge 0.87446$ [1], by a rounding scheme that picks a random threshold function from a distribution found by computer search; the ratio is certified with interval arithmetic, and the code is public (jbrakensiek/max-dicut). The previous best, about 0.87401, came from a single threshold rounding of Lewin, Livnat and Zwick (2002) [2].
• A related problem. For MAX 2-AND, where negated variables are allowed, $0.87414 \le \alpha_{\text{2AND}} \le 0.87435$ [1], so MAX DI-CUT is strictly easier than MAX 2-AND, refuting a conjecture of Austrin.
• Without UGC. Approximating MAX DI-CUT within $12/13+\varepsilon$ is NP-hard (Trevisan, Sorkin, Sudan and Williamson, 2000) [6].

What would count as progress

• A rounding scheme whose ratio is certified above 0.87446, for example with the interval-arithmetic verification of [1]. The authors conjecture that distributions over threshold roundings are enough to reach the optimum.
• A distribution of SDP configurations that defeats every rounding scheme, giving a UGC-hardness bound below 0.87461.
• A proof that determines $\alpha_{\text{DI-CUT}}$ exactly, or a better unconditional NP-hardness bound than $12/13$.

References

1. J. Brakensiek, N. Huang, A. Potechin and U. Zwick, Separating MAX 2-AND, MAX DI-CUT and MAX CUT, FOCS 2023; SIAM J. Comput. 55(3) (2026). arXiv:2212.11191
2. M. Lewin, D. Livnat and U. Zwick, Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems, IPCO 2002, LNCS 2337, 67–82. doi:10.1007/3-540-47867-1_6
3. U. Feige and M. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, ISTCS 1995, 182–189. doi:10.1109/ISTCS.1995.377033
4. M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42(6) (1995), 1115–1145. doi:10.1145/227683.227684
5. S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37(1) (2007), 319–357. doi:10.1137/S0097539705447372
6. L. Trevisan, G. B. Sorkin, M. Sudan and D. P. Williamson, Gadgets, approximation, and linear programming, SIAM J. Comput. 29(6) (2000), 2074–2097. doi:10.1137/S0097539797328847

Source

Imported from TCS Open Problems, Problem 1, curated by Kunal Marwaha. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.