I encountered this sub-problem while working on a problem about robustness of networks against link failures. Suppose we have an undirected graph $G=(V,E)$ such that edges in $E$ have weights taking values from $\{-1,+1\}$. We define the cut-set for $S\subseteq V$ as the set of edges connecting nodes in $S$ to those in $V\backslash S$ (the standard definition), and the cut value of the cut-set as the sum of weights of the edges in it.
It is known that one can find the cut-set with least cut value (min-cut) in polynomial time (in terms of |V|, |E|). I am interested in finding the cut-set whose cut value is the least and greater than zero (i.e., number of edges of weight +1 exceeds the number of edges of weight -1 in the cut-set) - does there exist a polynomial-time algorithm for generating such a cut-set?