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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.