[Solved]: Finding an exactly weighted st-path in a digraph

Problem Detail: 

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.

Asked By : Tyler Durden

Answered By : R B

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30106

3.2K people like this

 Download Related Notes/Documents