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 Graph G 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.


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.