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?

$\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$ Jun 6, 2016 at 10:32

1 Answer 1

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

$\endgroup$
1

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .