Suppose we have a graph $G(V, E)$. Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$.
Create a random modification of the graph:
- Drop each existing edge with probability $\alpha$.
- Add edges between the node-pairs that don't already have an edge with probability $\beta$.
Is it possible to say something about the expected size of the min-cut in the modified graph? (possibly under some extra assumptions)