Max Sum Product Multi-objective Shortest path problem

Question

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?

Answer 1

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.

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