# Random Optimization on Graphs: Minimum Cut

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 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
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!