1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.