# Is this problem #P-hard and why?

Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ are two nodes in $G$ and $k$ is a positive integer. What is the probability of the event that the shortest path from $s$ to $t$ has length at least $k$?

I feel this problem should be #P-hard, but I have no idea how to prove its #P-hardness.

I know I should choose a known #P-complete problem, and reduce it to the problem above. But I don't know which one to choose.

• If the distribution on edges gives them weight 1 with probability p and infinity (or anything larger than k) with probability 1-p, then I think this is #P-hard for k=3 by reduction from positive partitioned 2-DNF assignment counting. (Provan and Ball, 1983.) Does this help? or do the distributions have to be geometric? – a3nm Nov 16 '15 at 15:34
• In think if the distribution is binary it is easy to prove. So I let the distribution defined on all the positive integers. I wonder if it is true to all discrete distributions defined on the positive integers except for geometric distribution. It feels like such problem is harder than the binary case, but I can not prove. – Wieshawn Nov 16 '15 at 15:46

## 1 Answer

I show a reduction from positive partitioned 2-DNF assignment counting (see proof of 5.1 in [http://www.vldb.org/conf/2004/RS22P1.PDF] for details and inspiration of my proof). This problem asks to count the number of valuations that satisfy a formula of the form $\Phi: \bigvee_{(i,j) \in E} X_i Y_j$ with $E \subseteq \mathbb{N}^2$, where the $X_i$ and $Y_j$ are pairwise distinct variables.

Represent the positive partitioned 2-DNF as one vertex $x_i$ per variable $X_i$ and one vertex $y_j$ per variable $X_j$ and an edge from $x_i$ to $y_j$ for each $(i, j) \in E$.

I add a source vertex $s$ and an edge from $s$ to each $x_i$ with parameter $p=1/2$, so with probability $1/2$ the distance is $1$ and with probability $1/2$ it is $>1$. Likewise I add an edge from each $y_j$ to the target vertex $t$ with the same distribution. Up to the exact value of edges with length $>1$, is a clear probability-preserving bijection between valuations of the $X_i$ and $Y_j$ and possible worlds of this graph: for a valuation $\nu$, the corresponding graph is the one where the probabilistic edge adjacent to $X_i$ has length $1$ iff $\nu(X_i) = 1$ and length $>1$ otherwise, and likewise for the $Y_j$.

I set $k=3$. I claim that the probability that there is a path from $s$ to $t$ is the number of valuations that satisfy $\Phi$ divided by $2^N$, where $N$ is the number of variables. Indeed this is clear as a valuation is true iff some adjacent pair of $X_i$ and $Y_j$ is true iff the incident edges to the corresponding $x_i$ and $y_j$ both have length $1$ in the corresponding world. Note that the exact length of any edge of length $>1$ is irrelevant as the structure of the graph ensures it can never be part of a path of length $3$ from $s$ to $t$: there are only edegs from $s$ to the $x_i$, from the $x_i$ to the $y_j$, and from the $y_j$ to $t$.