Let $G = (V, E)$ be a directed graph. For $v\in V$, let $X_v \sim \mathcal B(p_v)$ with $p_v\in [0,1]$ a binary random variable. For $v, w \in V$, $Y_{v,w} = 1$ if there is a path from $v$ to $w$ with all vertices $u$ such that $X_u = 1$ and $Y_{v,w}$. I am trying to find a polynomial algorithm to compute the $P(Y_{s,t} = 1)$ for fixed two vertices $s,t\in V$. I know that if I enumerate all paths from $s$ to $t$, I can easily calculate the probability. But since the number of paths could be exponnential, this method is not polynomial. Can anyone help me?

  • $\begingroup$ Does $G$ happen to be acyclic? If so you can successively calculate the prob to go from $s$ to $u$ for each $u$, layer by layer in the BFS-tree rooted at $s$. But (I think) this won't work if $G$ has cycles. $\endgroup$
    – antkam
    Jun 22, 2020 at 17:19
  • $\begingroup$ I think that $G$ is general. Thank you for the idea of acyclic case $\endgroup$
    – Kroki
    Jun 23, 2020 at 2:17


You must log in to answer this question.

Browse other questions tagged .