Shortest absolute value of path in graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T00:02:14Z http://mathoverflow.net/feeds/question/90927 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90927/shortest-absolute-value-of-path-in-graph Shortest absolute value of path in graph Charles Bailey 2012-03-11T19:45:14Z 2012-03-12T04:10:40Z <p>Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.</p> <p>Is there an algorithm that determines whether there is a path of weight zero between vertices A and B? The Bellman-Form algorithm finds the path of smallest weight - is there another algorithm that determines the path of smallest absolute value weight?</p> <p>Thanks, Charles</p> http://mathoverflow.net/questions/90927/shortest-absolute-value-of-path-in-graph/90960#90960 Answer by Brendan McKay for Shortest absolute value of path in graph Brendan McKay 2012-03-12T04:10:40Z 2012-03-12T04:10:40Z <p>It is NP-complete if \$c\$ is not specified. For a set of numbers \$m_1,\ldots,m_t\$ make a digraph with vertices \$v_0,v_1,\ldots,v_t\$. From \$v_{i+1}\$ to \$v_i\$ put two edges, of length \$m_i\$ and \$-m_i\$, for each \$i\$. A path of zero length from \$v_0\$ to \$v_t\$ corresponds to a partition of \$m_1,\ldots,m_t\$ into two sets of equal size, which is a well known NP-complete problem (called PARTITION).</p>