Given a weighted directed graph $G = (V, E,w)$, its minimum cut is the nonempty $S \subsetneq V$ minimizing the weight of edges from $S$ to $V\setminus S$. Finding such a minimum cut is called the Directed Mincut Problem. Until very recently, solving this problem efficiently, that is in almost-linear $m^{1 + o(1)}$ time, was one of the flagship open problems in the field of fast graph algorithms. It served as a marker of the relative limitations of our techniques for directed vs. undirected graph problems.
In this talk I will describe a shockingly simple almost-linear time algorithm for directed mincut. The algorithm is more than simple enough to be covered in a graduate algorithms course, and improves on the previous best running time of ~$m\sqrt{n}$ by Cen et al. [FOCS ‘21].
This algorithm was discovered by me prompting GPT-6 Astra and providing very limited guidance. A complete exposition of the result, written by me and my coauthors Jason Li, Thatchaphol Saranurak, and Benyu Wang, can be found here: arXiv:2610.10898.
