<p>This problem is NP-complete.</p>

<p>Here's a simple reduction from MAXCUT:</p>

<p>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).</p>

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

<p>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|$.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-03-12T18:58:25.347Z
2014-03-13T08:30:01.623Z
2014-03-13T08:30:01.623Z
R B
<p>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.</p>

<p>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?  </p>

CC BY-SA 3.0
2014-03-13T17:31:31.370Z
"one can find the cut-set with least cut value (min-cut) in polynomial time" It is not true in your case. min-cut is NP-hard if there are negative weighted edges. Consider a graph where every edge has weight $-1$. Every min-cut is an unweighted max-cut.
Chao Xu
<graph-theory><graph-algorithms>
Finding a special cut-set in an weighted undirected graph
fenrir
# Finding a special cut-set in an weighted undirected graph

(Asked by: username_0 on 2014-03-12)

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?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: "one can find the cut-set with least cut value (min-cut) in polynomial time" It is not true in your case. min-cut is NP-hard if there are negative weighted edges. Consider a graph where every edge has weight $-1$. Every min-cut is an unweighted max-cut.  

---

## 1 answers

### Answer by username_2 on 2014-03-12. Score: 1 | Accepted answer

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.


---

