Approximating Directed Connectivity in Almost-Linear Time

Kent Quanrud

We present randomized algorithms that compute $(1+\epsilon )$-approximate minimum global edge and vertex cuts in weighted directed graphs in $O({\log }^4(n)/\epsilon )$ and $O({\log }^5(n)/\epsilon )$ single-…