Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.
The question is: given 2 nodes $v_1$ and $v_2$, is there a path from $v_1$ to $v_2$ with a weight $w$.
I would like to know if there are any known complexity results for this problem, or even anything related to this but with a specific weight, and not just shortest path, longest path etc.
This problem is NP-complete.
A reduction from subset sum:
Given numbers $\{x_1,\ldots,x_n\}$ and a target number $T$, construct the complete transitive acyclic graph $G=(\{x_1,\ldots,x_n\}\cup \{v_1,v_2\}, E)$,
Where $E=\{(v_1,x_i) \mid i\in [n]\}\cup \{(x_i,v_2) \mid i\in [n]\}\cup \{(x_i,x_j) \mid 1\leq i<j\leq n\}$, and $w(x_i,v_2)=0$, $w(v_1,x_j)=w(x_i,x_j)=x_j$.
Now simply ask if there exists a $v_1\leadsto v_2$ path of weight $T$.
This problem is NP-complete.
The "$\in$ NP"-part is trivial.
For the NP-hard part we reduce directed hamiltonian path:
Given a directed graph $G=(V,E)$ and two vertices $v_1,v_2\in V$, is there a path from $v_1$ to $v_2$, that visits each vertex exactly once?
For the reduction we keep $G$, $v_1$, and $v_2$ and number the nodes from $1$ to $n$, so that $v_2$ gets the number $n$. Then we assign each edge from node $i$ to node $j$ the weight $2^n+2^i$ and ask for a path of weight $n\cdot 2^n-1$.
It is easy to compute, that a hamiltonian path will have the correct weight.
For the other direction note that any path that takes $n$ steps or more would have a weight above $n\cdot 2^n$ and thus be invalid. A path that only takes $n-2$ or fewer steps on the other hand would have a weight below $(n-1)\cdot 2^n$, which is also invalid. So any valid path will have a length of $n-1$.
Furthermore the required weight has the bit for $2^i$ set to $1$ for each $0<i<n$. In order to achieve this without visiting node $i$, we would need to visit node $i-1$ (or a node with a smaller number) multiple times. But we only have $n-1$ steps to set $n-1$ bits. So only hamiltonian paths can achieve the correct weight.
The reduction works in polynomial time, since the size of the binary encoding of the weights and target is linear in the number of nodes.
