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