5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Shouldn't c be in (0,n) with n the number of vectors ? $\endgroup$
    – Denis
    Jun 3, 2016 at 15:19
  • $\begingroup$ 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). $\endgroup$
    – Nathanaël Fijalkow
    Jun 6, 2016 at 10:32

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1

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.