On computing minimum (s,t)-cuts in digraphs

Let D=(V,E) be a simple digraph with n vertices and m edges, and s and t be vertices designated as a source and a sink. The currently fastest algorithm that computes a minimum (s,t)-cut in D runs in O(min{ν,n2/3,m1/2}m) time, where ν is the size of a minimum (s,t)-cut. In this paper, we define the non-eulerianness μ as the sum of |#incoming edges at u−#outgoing edges at u| over all u∈V−{s,t}, and prove that a minimum (s,t)-cut in D can be obtained in O(min{m+ν(ν+μ)1/2n,(ν+μ)1/6nm2/3}) time. This outperforms the previous algorithm when D is a dense digraph with small μ.