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! 



Random Optimization on Graphs: Minimum Cut
As noted in the answer by Puck Rombach, the problem is NP-hard for fixed weights. However the OP asked about random IID weights. In this case finding the mincut or maxcut is still not known to be in P, but there is a polynomial-time algorithm to find a local maxcut (see [2], which refines the ideas of [1]).


[1] Michael Etscheid and Heiko R¨oglin. Smoothed analysis of local search for the maximum-cut problem. ACM Transactions on Algorithms (TALG), 13(2):25, 2017.


[2] Omer Angel, Sebastien Bubeck, Yuval Peres, and Fan Wei. Local max-cut in smoothed polynomial time. In Proceedings of the 49th Annual ACM SIGACT Sym. on Theory of Computing, pages 429–437. ACM, 2017.


