<p>This problem is PP-hard under Turing reductions when your weights are encoded in binary. The lower bound follows by a reduction from the $K$-th largest subset problem. Given a set $S\subseteq \{ s_1,\ldots,s_n \}\subseteq \mathbb{N}$ and $B, K\in \mathbb{N}$, this problem asks whether
\begin{align*}
\# \{ S'\subseteq S : \sum_{s\in S'} s \le B \} \ge K.
\end{align*}
It has recently been <a href="http://arxiv.org/abs/1501.06729" rel="nofollow">shown</a> that this problem is PP-complete under polynomial-time Turing reductions. It's easily seen how to encode this problem into yours (and see Proposition 4 in <a href="http://link.springer.com/chapter/10.1007/978-3-540-31982-5_9" rel="nofollow">here</a> in case you need some inspiration).</p>

<p>If $k_1$ is given in unary then your problem is PP-complete. If $k_1$ is given in binary then your problem is in PEXP, I cannot say if it is PEXP-complete.</p>

<p>In general, you often see this kind of problems in the setting of quantitative verification of (stochastic) systems.</p>

CC BY-SA 3.0
2015-09-28T13:32:21.077Z
2015-09-28T13:32:21.077Z
Christoph Haase
<p>I have a problem in graph theory and search the name and the complexity of the following problem :</p>

<p>Let $G = (V,A)$ be a directed graph, $p : A \rightarrow \mathbb{N}$ be a weight on the arcs of $G$ and $k_1, k_2\in \mathbb{N}$.</p>

<p>Is there a walk $w$ of $G$ of length $k_1$ ($w = (v_{i_1} \ldots v_{i_{k_1}})$) such that $\sum_{j = 1}^{n-1}p((v_{i_j},v_{i_{j+1}})) \leq k_2$ ?</p>

<p>Can you help to find the name and the complexity of this problem ?
Anybody has ever read something on this?</p>

<graph-theory>
weighted directed Walk in a graph
Cazaux B.
# weighted directed Walk in a graph

(Asked by: username_0 on 2015-09-28)

I have a problem in graph theory and search the name and the complexity of the following problem :

Let $G = (V,A)$ be a directed graph, $p : A \rightarrow \mathbb{N}$ be a weight on the arcs of $G$ and $k\_1, k\_2\in \mathbb{N}$.

Is there a walk $w$ of $G$ of length $k\_1$ ($w = (v\_{i\_1} \ldots v\_{i\_{k\_1}})$) such that $\sum\_{j = 1}^{n-1}p((v\_{i\_j},v\_{i\_{j+1}})) \leq k\_2$ ?

Can you help to find the name and the complexity of this problem ?
Anybody has ever read something on this?

**Tags:** graph-theory

---

## 1 answers

### Answer by username_1 on 2015-09-28. Score: 1

This problem is PP-hard under Turing reductions when your weights are encoded in binary. The lower bound follows by a reduction from the $K$-th largest subset problem. Given a set $S\subseteq \{ s\_1,\ldots,s\_n \}\subseteq \mathbb{N}$ and $B, K\in \mathbb{N}$, this problem asks whether
\begin{align\*}
\# \{ S'\subseteq S : \sum\_{s\in S'} s \le B \} \ge K.
\end{align\*}
It has recently been [shown](http://arxiv.org/abs/1501.06729) that this problem is PP-complete under polynomial-time Turing reductions. It's easily seen how to encode this problem into yours (and see Proposition 4 in [here](http://link.springer.com/chapter/10.1007/978-3-540-31982-5_9) in case you need some inspiration).

If $k\_1$ is given in unary then your problem is PP-complete. If $k\_1$ is given in binary then your problem is in PEXP, I cannot say if it is PEXP-complete.

In general, you often see this kind of problems in the setting of quantitative verification of (stochastic) systems.


---

