January 12, 2024 | Monika Henzinger, Jason Li, Satish Rao, Di Wang
This paper presents a deterministic algorithm for finding the minimum cut in a weighted graph in near-linear time. The algorithm improves upon previous results by providing a deterministic method that runs in near-linear time for weighted graphs, unlike earlier randomized algorithms. The main technique involves a clustering procedure that preserves minimum cuts. The algorithm builds on previous work by Kawarabayashi and Thorup, who developed a near-linear time algorithm for simple graphs, and by Li, who provided a deterministic algorithm for weighted graphs with a running time of $ m^{1+o(1)} $. The new algorithm extends these techniques to weighted graphs, addressing the challenges of preserving minimum cuts with a small error margin.
The algorithm uses a structural theorem that guarantees the existence of a sparse clustering that preserves minimum cuts in a weighted graph with a small multiplicative error. This clustering is constructed deterministically in near-linear time. The algorithm also addresses the challenge of reducing the polylogarithmic-approximate clusterings to a constant-approximate clustering, allowing for recursive applications. The algorithm's key contribution is the development of a deterministic graph decomposition that captures the essential properties required for the subsequent steps, leading to a nearly linear time complexity.
The algorithm proceeds by first approximating the minimum cut value $ \lambda $, then decomposing the graph into clusters that preserve the minimum cut with a small error. These clusters are further refined to ensure that the minimum cut is preserved with a small multiplicative factor. The algorithm then uses these clusters to construct a skeleton graph, which is used to find the minimum cut. The algorithm's efficiency is achieved by leveraging the properties of the clusters and the structure of the graph, ensuring that the minimum cut is preserved with high accuracy.
The algorithm's correctness is supported by several lemmas that show the progress of the clustering process and the preservation of the minimum cut. The algorithm's time complexity is nearly linear, making it efficient for large graphs. The algorithm's approach combines techniques from previous work, including the use of expander decompositions and local flow computations, to achieve a deterministic near-linear time minimum cut algorithm for weighted graphs.This paper presents a deterministic algorithm for finding the minimum cut in a weighted graph in near-linear time. The algorithm improves upon previous results by providing a deterministic method that runs in near-linear time for weighted graphs, unlike earlier randomized algorithms. The main technique involves a clustering procedure that preserves minimum cuts. The algorithm builds on previous work by Kawarabayashi and Thorup, who developed a near-linear time algorithm for simple graphs, and by Li, who provided a deterministic algorithm for weighted graphs with a running time of $ m^{1+o(1)} $. The new algorithm extends these techniques to weighted graphs, addressing the challenges of preserving minimum cuts with a small error margin.
The algorithm uses a structural theorem that guarantees the existence of a sparse clustering that preserves minimum cuts in a weighted graph with a small multiplicative error. This clustering is constructed deterministically in near-linear time. The algorithm also addresses the challenge of reducing the polylogarithmic-approximate clusterings to a constant-approximate clustering, allowing for recursive applications. The algorithm's key contribution is the development of a deterministic graph decomposition that captures the essential properties required for the subsequent steps, leading to a nearly linear time complexity.
The algorithm proceeds by first approximating the minimum cut value $ \lambda $, then decomposing the graph into clusters that preserve the minimum cut with a small error. These clusters are further refined to ensure that the minimum cut is preserved with a small multiplicative factor. The algorithm then uses these clusters to construct a skeleton graph, which is used to find the minimum cut. The algorithm's efficiency is achieved by leveraging the properties of the clusters and the structure of the graph, ensuring that the minimum cut is preserved with high accuracy.
The algorithm's correctness is supported by several lemmas that show the progress of the clustering process and the preservation of the minimum cut. The algorithm's time complexity is nearly linear, making it efficient for large graphs. The algorithm's approach combines techniques from previous work, including the use of expander decompositions and local flow computations, to achieve a deterministic near-linear time minimum cut algorithm for weighted graphs.