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）引入的框架，该框架用于解决无权有向图中的最小顶点割问题。此外，为了获得全局最小顶点割问题的结果，我们提出了一种新颖的黑盒归约方法，将该问题归约至其有根变体。在我们的工作之前，此类归约仅适用于更受限的场景，例如所有顶点权重为单位权重的情况。