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 iin [n]}cup {(x_i,v_2) mid iin [n]}cup {(x_i,x_j) mid 1leq i<jleq 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_1leadsto v_2$ path of weight $T$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30106 3.2K people like this
