<p>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|$. </p>

<p>Create a random modification of the graph: </p>

<ul>
<li>Drop each existing edge with probability $\alpha$. </li>
<li>Add edges between the node-pairs that don't already have an edge with probability $\beta$. </li>
</ul>

<p>Is it possible to say something about the expected size of the min-cut in the modified graph? (possibly under some extra assumptions) </p>

CC BY-SA 4.0
2018-06-15T22:21:43.867Z
was thinking that moving to the "math" forum might be a better place for this ...
Daniel
CC BY-SA 4.0
2018-06-22T11:31:37.473Z
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
CC BY-SA 4.0
2018-06-22T11:32:53.813Z
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
<pr.probability><randomized-algorithms><random-graphs>
Expected size of the min-cut, under edge perturbations
Daniel
# Expected size of the min-cut, under edge perturbations

(Asked by: username_0 on 2018-06-15)

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)

**Tags:** pr.probability, randomized-algorithms, random-graphs
> **Comments:**
> **username_0**: was thinking that moving to the "math" forum might be a better place for this ...  
> **username_1**: 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$.  
> **username_1**: 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.  

---

## 0 answers

