Finding a special cut-set in an weighted undirected graph

Question

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?

Answer 1

This problem is NP-complete.

Here's a simple reduction from MAXCUT:

Given an input graph $G$, we create a new graph $G'=G\cup K_{n^2}$ (i.w. add a separated clique over $n^2$ vertices).

We can now set the weight to be $-1$ for the original graph edges, and $1$ for the edges of the clique.

Claim: If $G$ has a max cut $(S,\bar S = V\setminus S)$ such that $|E\cap (S\times \bar S)| = k$, then $G'$ has a minimal "special cut-set" whose value is $|n^2-k-1|$.

Proof: Since the special cut set's value is required to be positive, $S\cap K_{n^2}$ is neither empty or the entire clique. Since the contribution from the negatively weighted edges of $G$ less than $n^2-1$, we can conclude that $|S\cap K_{n^2}|\in \{1,n-1\}$, and it's contribution to the special cut value is $n^2-1$.

Now the set intersection with $G$ has to be the max cut of $G$, as all of the weights are negative, which contributes another $k$ to the special cut value.