1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Chao Xu Mar 13 '14 at 17:31
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.