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?