Reproduce “Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Antoine El-Hayek, Monika Henzinger, Jason Li
The paper by El-Hayek, Henzinger, and Li at IST Austria introduces a deterministic fully-dynamic minimum cut algorithm for unweighted graphs that operates in n^o(1) amortized update time and supports minimum cut sizes up to 2^Θ(log^(3/4-c) n). Additionally, they develop the first (1+ε)-approximate fully-dynamic minimum cut algorithm for weighted graphs, achieving n^o(1) randomized update time for ε ≥ 2^−Θ(log^(3/4−c) n).
Key insights
- Derandomizing local minimum cut procedures is feasible by combining tree packing and color coding, enabling deterministic algorithms in dynamic settings.
- Careful dynamic adaptation of static "fragmenting" techniques allows maintaining tight approximation guarantees (1+2δ) per recursive step in a cluster hierarchy.
- A hierarchical decomposition, coupled with efficient localized cut detection and recursive contraction, can yield exact solutions for superpolylogarithmic cut sizes in subpolynomial time.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.