<p>I show a reduction from positive partitioned 2-DNF assignment counting (see proof of 5.1 in [<a href="http://www.vldb.org/conf/2004/RS22P1.PDF]" rel="nofollow">http://www.vldb.org/conf/2004/RS22P1.PDF]</a> 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.</p>

<p>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$.</p>

<p>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 $&gt;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 $&gt;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 $&gt;1$ otherwise, and likewise for the $Y_j$.</p>

<p>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 $&gt;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$.</p>

CC BY-SA 3.0
2015-11-16T16:09:13.370Z
2015-11-16T16:09:13.370Z
Antoine Amarilli 'a3nm'
<blockquote>
  <p>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$?</p>
</blockquote>

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

<p>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.</p>

CC BY-SA 3.0
2015-11-16T15:34:20.350Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-11-16T15:46:21.833Z
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
<cc.complexity-theory><np-hardness><complexity-classes>
Is this problem #P-hard and why?
Wieshawn
# Is this problem #P-hard and why?

(Asked by: username_0 on 2015-11-16)

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

**Tags:** cc.complexity-theory, np-hardness, complexity-classes
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2015-11-16. Score: 0 | Accepted 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$.


---

