<p>It seems NP-complete even with weights in $\{0,1\}$.
I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses.
More precisely, an instance is a CNF formula, and an integer $k$, and you have to say whether there is an assignment satisfying at most $k$ clauses.
It is shown to be NP-complete in <a href="https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/1185/minsat.pdf" rel="nofollow">this paper</a>.</p>

<p>Start from a MINSAT instance with variables $x_1\dots x_n$ and clauses $C_1\dots C_m$, we build an instance of your problem.
The weight vector has $m$ coordinates (the number of clauses).
The first edge of the graph puts every coordinate to $1$.
Then we traverse $n$ nodes where you have to choose the truth value of the variables $x_1\dots x_n$. For instance if you set $x_i$ to true, the corresponding edge vector contains a $0$ for each clause $C_j$ where $x_i$ appears positively and $1$ elsewhere.
The idea is that a clause is set to $0$ if the assignment makes it true. Since you use the product to evaluate a path, $0$ is absorbing and corresponding to the wanted disjunction.
Finally, you have a path from the source to the target with weight at least $m-k$ if and only if there is an instanciation of variables satisfying at most $k$ clauses.</p>

<p><strong>Reference</strong>: The Minimum Satisfiability Problem, Kohli, Krishnamurti, Mirchandani in Journal SIAM Journal on Discrete Mathematics 1994</p>

CC BY-SA 3.0
2016-06-06T10:40:07.710Z
Thanks Denis! It does answer the question. However, I actually forgot a crucial parameter in the question. Please see there a follow-up question, which is not covered by your answer: http://cstheory.stackexchange.com/questions/35909/constant-width-max-sum-product-multi-objective-shortest-path-problem
Nathanaël Fijalkow
CC BY-SA 3.0
2016-06-03T15:15:53.717Z
2016-06-03T17:49:56.647Z
2016-06-03T17:49:56.647Z
Denis
<p>Is anything known about the following problem:</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.
A path is first assigned a vector, which is the component-wise <strong>product</strong> of the weights of the edges along the path. 
The path is then assigned a value, which is the <strong>sum</strong> of the entries of this vector.
I am interested in the <strong>maximum</strong> 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>Is this problem in PTIME or NP-complete?</p>

CC BY-SA 3.0
2016-06-03T15:19:41.487Z
Shouldn't c be in (0,n) with n the number of vectors ?
Denis
CC BY-SA 3.0
2016-06-06T10:32:29.340Z
Indeed @Denis, a priori c is in (0,n). In my case (stochastic), the sum of the components in each vector sums to 1 (at most), so c is in (0,1).
Nathanaël Fijalkow
<graph-algorithms><np-hardness><shortest-path><stochastic-process>
Max Sum Product Multi-objective Shortest path problem
Nathanaël Fijalkow
# Max Sum Product Multi-objective Shortest path problem

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

Is anything known about the following problem:

I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1.
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?

Is this problem in PTIME or NP-complete?

**Tags:** graph-algorithms, np-hardness, shortest-path, stochastic-process
> **Comments:**
> **username_1**: Shouldn't c be in (0,n) with n the number of vectors ?  
> **username_0**: Indeed @Denis, a priori c is in (0,n). In my case (stochastic), the sum of the components in each vector sums to 1 (at most), so c is in (0,1).  

---

## 1 answers

### Answer by username_1 on 2016-06-03. Score: 2 | Accepted answer

It seems NP-complete even with weights in $\{0,1\}$.
I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses.
More precisely, an instance is a CNF formula, and an integer $k$, and you have to say whether there is an assignment satisfying at most $k$ clauses.
It is shown to be NP-complete in [this paper](https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/1185/minsat.pdf).

Start from a MINSAT instance with variables $x\_1\dots x\_n$ and clauses $C\_1\dots C\_m$, we build an instance of your problem.
The weight vector has $m$ coordinates (the number of clauses).
The first edge of the graph puts every coordinate to $1$.
Then we traverse $n$ nodes where you have to choose the truth value of the variables $x\_1\dots x\_n$. For instance if you set $x\_i$ to true, the corresponding edge vector contains a $0$ for each clause $C\_j$ where $x\_i$ appears positively and $1$ elsewhere.
The idea is that a clause is set to $0$ if the assignment makes it true. Since you use the product to evaluate a path, $0$ is absorbing and corresponding to the wanted disjunction.
Finally, you have a path from the source to the target with weight at least $m-k$ if and only if there is an instanciation of variables satisfying at most $k$ clauses.

**Reference**: The Minimum Satisfiability Problem, Kohli, Krishnamurti, Mirchandani in Journal SIAM Journal on Discrete Mathematics 1994

> **Comments:**
> **username_0**: Thanks Denis! It does answer the question. However, I actually forgot a crucial parameter in the question. Please see there a follow-up question, which is not covered by your answer: http://cstheory.stackexchange.com/questions/35909/constant-width-max-sum-product-multi-objective-shortest-path-problem  

---

