Deterministic Near-Linear Time Minimum Cut in Weighted Graphs

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs

January 12, 2024 | Monika Henzinger*, Jason Li†, Satish Rao‡, Di Wang§
This paper presents the first deterministic algorithm that finds a minimum cut in weighted graphs in near-linear time. The main technique involves a clustering procedure that perfectly preserves minimum cuts. The authors build on previous work by Kawarabayashi and Thorup, which provided a near-linear time algorithm for simple graphs, and Li, who gave an almost-linear time deterministic algorithm for weighted graphs using expander decompositions. The key contributions include a structural theorem that guarantees the existence of a sparse clustering that preserves minimum cuts with a polylogarithmic error, and a modified graph decomposition technique inspired by unweighted graph algorithms. The algorithmic approach combines hierarchical clustering, tree packing, and dynamic programming to efficiently find the minimum cut. The paper also discusses the challenges and improvements made in handling weighted graphs compared to simple graphs, particularly in dealing with the complexity of local flow computations and the allocation of sources for these computations. The overall goal is to achieve a near-linear time complexity while maintaining the accuracy of minimum cut preservation.This paper presents the first deterministic algorithm that finds a minimum cut in weighted graphs in near-linear time. The main technique involves a clustering procedure that perfectly preserves minimum cuts. The authors build on previous work by Kawarabayashi and Thorup, which provided a near-linear time algorithm for simple graphs, and Li, who gave an almost-linear time deterministic algorithm for weighted graphs using expander decompositions. The key contributions include a structural theorem that guarantees the existence of a sparse clustering that preserves minimum cuts with a polylogarithmic error, and a modified graph decomposition technique inspired by unweighted graph algorithms. The algorithmic approach combines hierarchical clustering, tree packing, and dynamic programming to efficiently find the minimum cut. The paper also discusses the challenges and improvements made in handling weighted graphs compared to simple graphs, particularly in dealing with the complexity of local flow computations and the allocation of sources for these computations. The overall goal is to achieve a near-linear time complexity while maintaining the accuracy of minimum cut preservation.
Reach us at info@study.space
[slides] Deterministic Near-Linear Time Minimum Cut in Weighted Graphs | StudySpace