Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

2024/01/18 by Wenyu Jin, Jin, Wenyu, Xiaorui Sun +3 · 3 citations
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2401.09700

openalex publication_date 2024/01/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n)^o(1). Previously, the best update time was \widetilde O(√(n)) for any c > 2 and c = O(log n) [Thorup, Combinatorica'07].

Cited by

• Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
• Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
• Simple Algorithms for Fully Dynamic Edge Connectivity

Related

• Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
• Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
• Practical Fully Dynamic Minimum Cut Algorithms
• Minimum Cuts in Near-Linear Time
• Minimum Cut in O(mlog² n) Time