Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then what is the expected maximum flow from $s$ to $t$? or the probability of the maximum flow exceeds some number $k$?
There are just a few articles in 1980s studied similar problem:
- "Flow in networks with random capacities" by GR Grimmett, DJA Welsh 1982
- "The maximal flow through a directed graph with random capacities" by GR Grimmett, WCS Suen 1982
They only studied the case where G is a tree or complete graph and the answer is pessimistic. They suspected the problem in general is not in the polynomial time hierarchy but without a proof.
My questions are
- What is the complexity class of this problem when both graph G and the probability distribution $F$ are general?
- What if $G$ and $E^*$ has some special structures, e.g. fixed tree width, bipartite (if $s$ and $t$ are removed) etc.?
- What if $F$ is simple enough, e.g. Bernoulli?
Any ideas and relevant references are appreciated.
edit: I am actually interested in a very special kind of graph like this so the center part of $G$ is bipartite $V \cup W$. All arcs from $s$ to $V$ have fixed capacity $c$, but all arcs from $W$ to $t$ have capacity random centered at $c$ (e.g. $Bernoulli$ between 0 and $2c$, or $Binomial (2c, 0.5)$ etc.). All arcs between $V$ and $W$ have infinite capacity.
I have some type of bipartite graphs that the expected maximum flow can be determined in polynomial time (in terms of number of node and the magnitute of $c$) for any discrete random capacities. Also there are some more complex bipartite graphs which I can only find polynomial time algorithm for Bernoulli capacity. I want to generalize this statement, either the problem is in NP or #P that a polynomial time algoirthm is unlikely, or it is actually can be determined in polynomial time.