<p>For K=2, PARTITION reduces to this problem, so it is NP-hard.</p>

<p>Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such that $\sum_{i\in I} x_i=\sum_{i\notin I}x_i$.</p>

<p>Let $S=\sum_{i\in[1,n]} x_i$, and $y_i=\exp(-\frac{x_i}S)$ for each $i$. Note that $y_i\in (0,1)$.</p>

<p>You build a graph with $n+1$ nodes $p_1,\dots ,p_n,p_{n+1}$.
You have two edges from $p_i$ to $p_{i+1}$: one with weight $(\frac{y_i}2,\frac12)$ and the other with weight $(\frac 12,\frac{y_i}2)$. The division by $2$ is there to ensure the additionnal constraint that the sum of coordinates is at most $1$.</p>

<p>A path from $p_1$ to $p_{n+1}$ corresponds to a partition $I$: you end up with the vector $$\big(\dfrac{\exp(-\frac1S\sum_{i\in I} x_i)}{2^n}~,~ \dfrac{\exp(-\frac1S\sum_{i\notin I} x_i)}{2^n}\big).$$
Since the minimum of $e^{-x}+e^{-(1-x)}$ is reached for $x=1/2$, there exists a path of weight $\exp(-1/2)/2^{n-1}$ if and only if there was a balanced Partition of the initial integer list.</p>

CC BY-SA 3.0
2016-12-17T00:12:14.040Z
I just realised (a few months later) that it does not answer the question, for two reasons. First, by "beat the threshold c" I mean being larger than or equal to c. Your reduction is for smaller than or equal to c. Second, and more serious: the encoding is not polynomial. Indeed, in PARTITION the x_i's are integers encoded in binary, and when encode the y_i's in binary as well they use exponentially many bits. To see this assume S = 1 (WLOG), if x = 2^n, then y = 2^{-2^n}, which uses 2^n bits in binary representation.
Nathanaël Fijalkow
CC BY-SA 3.0
2016-12-22T17:24:08.150Z
@user48878 yes it's an issue. In your initial problem, how are the weights given ? They are rational numbers given in binary or unary ?
Denis
CC BY-SA 3.0
2017-01-16T16:43:49.443Z
The weights are rational numbers given in binary, "as usual" :-)
Nathanaël Fijalkow
CC BY-SA 3.0
2017-01-16T17:47:59.663Z
ok, at least it shows that a succinct version of your problem where weights are of the form exp(x), x given in binary, is NP-hard. Is there a simpler way to show this fact ?
Denis
CC BY-SA 3.0
2016-06-06T12:57:22.980Z
2016-06-06T15:21:15.147Z
2016-06-06T15:21:15.147Z
Denis
<p>This question is a follow-up on the <a href="https://cstheory.stackexchange.com/questions/34886/max-sum-product-multi-objective-shortest-path-problem">question</a> I asked three days ago here.</p>

<p>For convenience I restate it here.</p>

<p>I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1, which sum up to 1 (at most). 
A path is first assigned a vector, which is the component-wise product of the weights of the edges along the path. The path is then assigned a value, which is the sum of the entries of this vector. I am interested in the maximum path.</p>

<p>More specifically, I consider the following decision problem: given a graph, a source, a target and a threshold c in (0,1), does there exist a path from the source to the target whose value beats the threshold c?</p>

<p>As @Denis has shown, this problem is NP-complete if the size of the vector is part of the input.</p>

<p>I am interested in the following restriction: now the size of the vectors (meaning, number of entries) is restricted to a constant K (not part of the input).
It is clear that the problem is polynomial for K = 1. Is it polynomial for K = 2? Is there K such that it is polynomial for K and NP-complete for K+1?</p>

<graph-algorithms><np-hardness><shortest-path><stochastic-process>
Constant Width Max Sum Product Multi-objective Shortest path problem
Nathanaël Fijalkow
# Constant Width Max Sum Product Multi-objective Shortest path problem

(Asked by: username_0 on 2016-06-06)

This question is a follow-up on the [question](https://cstheory.stackexchange.com/questions/34886/max-sum-product-multi-objective-shortest-path-problem) I asked three days ago here.

For convenience I restate it here.

I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1, which sum up to 1 (at most).
A path is first assigned a vector, which is the component-wise product of the weights of the edges along the path. The path is then assigned a value, which is the sum of the entries of this vector. I am interested in the maximum path.

More specifically, I consider the following decision problem: given a graph, a source, a target and a threshold c in (0,1), does there exist a path from the source to the target whose value beats the threshold c?

As @username_1 has shown, this problem is NP-complete if the size of the vector is part of the input.

I am interested in the following restriction: now the size of the vectors (meaning, number of entries) is restricted to a constant K (not part of the input).
It is clear that the problem is polynomial for K = 1. Is it polynomial for K = 2? Is there K such that it is polynomial for K and NP-complete for K+1?

**Tags:** graph-algorithms, np-hardness, shortest-path, stochastic-process


---

## 1 answers

### Answer by username_1 on 2016-06-06. Score: 4

For K=2, PARTITION reduces to this problem, so it is NP-hard.

Take an instance of PARTITION: a list of nonnegative integers $x\_1,\dots ,x\_n$, and you ask if there is a subset $I\subseteq [1,n]$ such that $\sum\_{i\in I} x\_i=\sum\_{i\notin I}x\_i$.

Let $S=\sum\_{i\in[1,n]} x\_i$, and $y\_i=\exp(-\frac{x\_i}S)$ for each $i$. Note that $y\_i\in (0,1)$.

You build a graph with $n+1$ nodes $p\_1,\dots ,p\_n,p\_{n+1}$.
You have two edges from $p\_i$ to $p\_{i+1}$: one with weight $(\frac{y\_i}2,\frac12)$ and the other with weight $(\frac 12,\frac{y\_i}2)$. The division by $2$ is there to ensure the additionnal constraint that the sum of coordinates is at most $1$.

A path from $p\_1$ to $p\_{n+1}$ corresponds to a partition $I$: you end up with the vector $$\big(\dfrac{\exp(-\frac1S\sum\_{i\in I} x\_i)}{2^n}~,~ \dfrac{\exp(-\frac1S\sum\_{i\notin I} x\_i)}{2^n}\big).$$
Since the minimum of $e^{-x}+e^{-(1-x)}$ is reached for $x=1/2$, there exists a path of weight $\exp(-1/2)/2^{n-1}$ if and only if there was a balanced Partition of the initial integer list.

> **Comments:**
> **username_0**: I just realised (a few months later) that it does not answer the question, for two reasons. First, by "beat the threshold c" I mean being larger than or equal to c. Your reduction is for smaller than or equal to c. Second, and more serious: the encoding is not polynomial. Indeed, in PARTITION the x_i's are integers encoded in binary, and when encode the y_i's in binary as well they use exponentially many bits. To see this assume S = 1 (WLOG), if x = 2^n, then y = 2^{-2^n}, which uses 2^n bits in binary representation.  
> **username_1**: @user48878 yes it's an issue. In your initial problem, how are the weights given ? They are rational numbers given in binary or unary ?  
> **username_0**: The weights are rational numbers given in binary, "as usual" :-)  
> **username_1**: ok, at least it shows that a succinct version of your problem where weights are of the form exp(x), x given in binary, is NP-hard. Is there a simpler way to show this fact ?  

---

