
arXiv: 2007.09018
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 k 𝒪(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \(\binom{V(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 -𝒪( k log k ). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2 -𝒪( k log k ) instead of 2 -𝒪( k 4 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 2 𝒪( k log k ) (|V(G)|+|E(G)|) on undirected graphs.
FOS: Computer and information sciences, Randomized algorithms, Parameterized complexity, tractability and kernelization, flow-augmentation, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), fixed-parameter tractability, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), graph separation problems, Flows in graphs
FOS: Computer and information sciences, Randomized algorithms, Parameterized complexity, tractability and kernelization, flow-augmentation, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), fixed-parameter tractability, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), graph separation problems, Flows in graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
