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

• We give a new approximation algorithm for the Min k-Size s–t Cut problem.
• The algorithm is very simple and has only three lines to state.
• We analyze the integrality gap of a natural LP for the 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)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+1k+1−k⁎, where k⁎k⁎ is the size of the s-side of an optimal solution.