# Expected size of the min-cut, under edge perturbations

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)

• was thinking that moving to the "math" forum might be a better place for this ... – Daniel Jun 15 '18 at 22:21
• Consider your two modification steps separately. The effect of the first one will depend highly on the structure of the graph. E.g. consider G1 consisting of a path of length n (with min cut 1) vs. G2 consisting of two n/2-cliques connected by a single edge (also having min cut 1). Dropping each edge with probability some small $\alpha>0$ will disconnect G1 with probability about $1-(1-\alpha)^n \approx \alpha n$. In contrast it will disconnect G2 with probability about $\alpha$. – Neal Young Jun 22 '18 at 11:31
• As for the second step, the min cut in the resulting graph is, up to a factor of two, the maximum of two quantities: (i) the min cut in the graph after step 1, and (ii) the min cut in the random graph that has each possible edge with probability $\beta$. The latter quantity is probably well-studied. – Neal Young Jun 22 '18 at 11:32