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)

  • $\begingroup$ was thinking that moving to the "math" forum might be a better place for this ... $\endgroup$ – Daniel Jun 15 '18 at 22:21
  • $\begingroup$ 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$. $\endgroup$ – Neal Young Jun 22 '18 at 11:31
  • $\begingroup$ 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. $\endgroup$ – Neal Young Jun 22 '18 at 11:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.