2020/07/17 by Eun Jung Kim, Kim, Eun Jung, Stefan Kratsch +5
Computer Science · Engineering · Mathematics · #Advanced Theoretical and Applied Studies in Material Sciences and Geometry #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Engineering Technology and Methodologies #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2007.09018
openalex publication_date 2020/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph G with distinguished vertices s,t ∈ V(G) and an integer k, one can in randomized kO(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \binomV(G)2 such that the following holds: for every inclusion-wise minimal st-cut Z in G of cardinality at most k, Z becomes a minimum-cardinality cut between s and t in G+A (i.e., in the multigraph G with all edges of A added) with probability 2-O(k log k). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2-O(k log k) instead of 2-O(k4 log k)), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective st-Cut problem can be solved in randomized FPT time 2O(k log k) (|V(G)|+|E(G)|) on undirected graphs.