Incremental Directed Minimum Cut by Dynamizing Gabow's Algorithm
2026-08-17 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors present the first algorithm that can update the smallest cut in a directed graph as edges are added, without having to start from scratch each time. Their method works for any size of the minimum cut value and runs efficiently over all insertions. This improves on earlier algorithms that were limited to undirected graphs or very small cut values. It builds directly on a well-known static algorithm but adapts it to handle changes incrementally without slowing down overall.
directed graphminimum cutincremental algorithmedge insertionglobal minimum cutGabow's algorithmdeterministic algorithmupdate timegraph algorithms
Authors
Thatchaphol Saranurak, Kaiyang Xie, Zhaienhe Zhou
Abstract
We give the first incremental algorithm for directed global minimum cut. Given a directed graph with $n$ vertices undergoing $m$ edge insertions, our deterministic algorithm explicitly maintains a global minimum cut or certifies that its value is at least $k$ in $O(km\log n)$ total update time. Prior work required either that $k\le2$ or that the graph is undirected. Our algorithm is a strict incremental extension of Gabow's state-of-the-art static algorithm (JCSS 1995), with no asymptotic loss in running time over the entire insertion sequence.