# Constant Width Max Sum Product Multi-objective Shortest path problem

This question is a follow-up on the question 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 @Denis 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?

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.

• 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. – user48878 Dec 17 '16 at 0:12
• @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 Dec 22 '16 at 17:24
• The weights are rational numbers given in binary, "as usual" :-) – user48878 Jan 16 '17 at 16:43
• 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 Jan 16 '17 at 17:47