We develop new $(1+ε)$-approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a directed vertex-weighted graph. Our algorithms are randomized, and have a running time of $O\left(m^{1+o(1)}/ε\right)$ on any $m$-edge $n$-vertex input graph, assuming all edge/vertex weights are polynomially-bounded. In particular, for any constant $ε>0$, our algorithms have an almost-optimal running time of $O\left(m^{1+o(1)}\right)$. The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is $\tilde{O}\left(\min\left\{n^2/ε^2,m^{1+o(1)}\sqrt{n}\right\}\right)$ for Minimum Edge-Cut, and $\tilde{O}\left(n^2/ε^2\right)$ for Minimum Vertex-Cut. Our results further extend to the rooted variants of the Minimum Edge-Cut and Minimum Vertex-Cut problems, where the algorithm is additionally given a root vertex $r$, and the goal is to find a minimum-weight cut separating any vertex from the root $r$. In terms of techniques, we build upon and extend a framework that was recently introduced by (Chuzhoy et al., SODA 2026) for solving the Minimum Vertex-Cut problem in unweighted directed graphs. Additionally, in order to obtain our result for the Global Minimum Vertex-Cut problem, we develop a novel black-box reduction from this problem to its rooted variant. Prior to our work, such reductions were only known for more restricted settings, such as when all vertex-weights are unit.

翻译：我们针对有向边加权图中的全局最小边割问题，以及有向顶点加权图中的全局最小顶点割问题，提出了新的$(1+ε)$-逼近算法。我们的算法是随机化的，在任意具有$m$条边、$n$个顶点的输入图上，假设所有边/顶点权重均为多项式有界，其运行时间为$O\\left(m^{1+o(1)}/ε\\right)$。特别地，对于任意常数$ε>0$，我们的算法具有近似最优的运行时间$O\\left(m^{1+o(1)}\\right)$。此前该问题最快的已知运行时间（由 Cen 等人于 FOCS 2021 提出）为：对于最小边割问题是$\\tilde{O}\\left(\\min\\left\\{n^2/ε^2,m^{1+o(1)}\\sqrt{n}\\right\\}\\right)$，对于最小顶点割问题是$\\tilde{O}\\left(n^2/ε^2\\right)$。我们的结果进一步推广到最小边割和最小顶点割问题的有根变体，其中算法额外给定一个根顶点$r$，目标是找到一个最小权重的割，用于分离任意顶点与根$r$。在技术层面，我们基于并扩展了由 Chuzhoy 等人（SODA 2026）最近提出的用于解决无权有向图中最小顶点割问题的框架。此外，为了获得全局最小顶点割问题的结果，我们开发了一种新颖的黑盒归约方法，将该问题归约到其有根变体。在我们的工作之前，此类归约仅在更受限的设置下已知，例如当所有顶点权重为单位权重时。