Path Length Existence Problems in Bounded-Treewidth Probabilistic Graphs

Antoine Amarilli, Mikaël Monet, Harshul Sagar

We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The lengt…