2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user48878 Dec 17 '16 at 0:12
  • $\begingroup$ @user48878 yes it's an issue. In your initial problem, how are the weights given ? They are rational numbers given in binary or unary ? $\endgroup$ – Denis Dec 22 '16 at 17:24
  • $\begingroup$ The weights are rational numbers given in binary, "as usual" :-) $\endgroup$ – user48878 Jan 16 '17 at 16:43
  • $\begingroup$ 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 ? $\endgroup$ – Denis Jan 16 '17 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.