Deterministic mincut in almost-linear time

DOI10.1145/3406325.3451114MaRDI QIDQ6087010zbMATH OpenOpenAlexFDO

Authors Jason Li

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.05513

zbMATH Keywords

de-randomizationdeterministic algorithmsgraph sparsificationminimum cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in $m^{1+o(1)}$ time, answering an open question of Karger from the 1990s. To obtain our result, we de-randomize the construction of the emph{skeleton} graph in Karger's near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.

Cited in

(18)

• scientific article; zbMATH DE number 1670649 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• scientific article; zbMATH DE number 6846417 (Why is no real title available?)
• Minimum cuts in near-linear time
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)
• scientific article; zbMATH DE number 7759280 (Why is no real title available?)
• An optimal pruned traversal tree-based fast minimum cut solver in dense graph
• Bisection width, discrepancy, and eigenvalues of hypergraphs
• On the streaming complexity of expander decomposition
• High-speed minimum cut approximation in dense graph using compacted pruned tree
• Applying a cut-based data reduction rule for weighted cluster editing in polynomial time
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Worst-case to expander-case reductions: derandomized and generalized
• A parameterized algorithm for vertex and edge connectivity of embedded graphs
• Deterministic minimum Steiner cut in maximum flow time
• Practical expander decomposition
• Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts
• Fully-dynamic min-cut

This page was built for publication: Deterministic mincut in almost-linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087010)