2025/12/09 by Ron Mosenzon, Mosenzon, Ron
Computer Science · Business, Management and Accounting · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Facility Location and Emergency Management
paper · pdf · doi:10.1145/3798129.3800732
We develop new (1+є)-approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a directed vertex-weighted graph. Our algorithms are randomized, and have a running time of O(m1+o(1)/є) on any m-edge n-vertex input graph, assuming all edge/vertex weights are polynomially-bounded. In particular, for any constant є>0, our algorithms have an almost-optimal running time of O(m1+o(1)). The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is O(minn2/є2,m1+o(1)√n) for Minimum Edge-Cut, and O(n2/є2) for Minimum Vertex-Cut.