Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) cuts of this graph, which one has the minimum weight? More concretely, $$ \min_{\sigma\in\{-1,1\}^n}\sum_{1\leq i <j\leq n, \sigma_i\neq \sigma_j}W_{ij} = \max_{\sigma\in\{-1,1\}^n}\sum_{1\leq i<j\leq n,\sigma_i=\sigma_j}W_{ij}. $$ How can we characterize such a minimum (maximum)?

My thoughts are as follows:

  1. Clearly, if $\sigma$ and $-\sigma$ have the same weights, they are in a sense equivalent.
  2. If $W_{ij}>0$ for every $i,j$, then trivially the optimum is $ \sigma=(+1,+1,\dots,+1)$ (and also, $(-1,-1,\dots,-1)$).
  3. So, the problem starts getting interesting, when the weight distribution also has some negative support.
  4. The objective can be expressed as, say, $$ \max_{\sigma\in\{-1,1\}^n}\sum_{1\leq i<j\leq n,\sigma_i=\sigma_j}W_{ij}=\max_{\sigma\in\{-1,1\}^n}\sum_{1\leq i<j\leq n}W_{ij}(\sigma_i+\sigma_j)^2. $$
  5. If $W_{ij}>0$, then assuming we do not assume a cut with $\sigma_i$ all $+1$ or $-1$, the Fulkerson-Ford algorithm finds the min-cut in polynomial time.

I would appreciate any input!


Your problem is not in P in general. If you allow negative weights on edges, then you may have a graph where no edges have positive weight, in which case the problem of finding a min cut is equivalent to finding a max cut if we take the absolute value of the weights. This is an NP-hard problem.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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