2
$\begingroup$

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.

$\endgroup$

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.