Random Optimization on Graphs: Minimum Cut

Question

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!

Answer 1

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.

Answer 2

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.