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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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$
    – Nathanaël Fijalkow
    Dec 17, 2016 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, 2016 at 17:24
  • $\begingroup$ The weights are rational numbers given in binary, "as usual" :-) $\endgroup$
    – Nathanaël Fijalkow
    Jan 16, 2017 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, 2017 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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