A new approximation algorithm for the unbalanced Min s–t Cut problem.

Being the unbalanced version of the famous Min s – t Cut problem, the Min k -Size s – t Cut problem asks to find a k -size s – t cut with the minimum capacity, where a k -size s – t cut means an s – t cut with its s -side having size at most k . This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k -Size s – t Cut problem is NP-hard and can be approximated within O ( log ⁡ n ) , where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k -Size s – t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k + 1 k + 1 − k ⁎ , where k ⁎ is the size of the s -side of an optimal solution. [ABSTRACT FROM AUTHOR]