Welcome to MathOverflow

Question

1

Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.

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?

Thanks, Charles

flag	asked Mar 11 2012 at 19:45 Charles Bailey 63●3

	What weights are allowable? Integers between -16 and 16? Arbitrary rational or real numbers? Something in between? (If there is a minimum gap between path weights, it might make the problem easier.) – Charles Staats Mar 11 2012 at 20:18
	The weights are integers in the interval [-c,c] for some integer constant c. – Charles Bailey Mar 11 2012 at 20:23
	If it's a finite graph, then of course there's an algorithm, exhaustive search. Perhaps your question is whether there is a more efficient algorithm? – Gerry Myerson Mar 11 2012 at 23:03
	Yes, it's a finite graph, so exhaustive search would work. I'm looking for something more efficient. Thanks, Charles – Charles Bailey Mar 12 2012 at 2:55

Brendan McKay · Accepted Answer · 2012-03-12 04:10:40Z UTC

6

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

answered Mar 12 2012 at 4:10

Brendan McKay
9,179●1●15●34

	That still leaves the question of whether any practical algorithms exist, at least to find "small" absolute values. There is the obvious convex relaxation, but it is not clear it works at all... – Igor Rivin Mar 12 2012 at 4:35
	for weights given in unary, one might suspect that there will be a dynamic programming algorithm... – Dima Pasechnik Mar 13 2012 at 5:06
	If the weights are integers of magnitude $O(c)$, then there is an $O(cnm)$ dynamic programming algorithm, where $m$ is the number of edges. For each vertex in topological order, determine which path lengths occur from the starting vertex to that vertex. It would be nice to know if faster is possible. – Brendan McKay Mar 13 2012 at 6:58

Shortest absolute value of path in graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.