0
$\begingroup$

Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a function of the weights of its edges. Can we still use Bellman-Ford to converge to the shortest (i.e., minimum weight) path from some source $S$ to some sink $T$ after some number of iterations? Would Bellman-Ford converge eventually?

Follow up question:

The particular path weight function I am interested in uses a set operation where each edge is associated with a set of items. Each item has a weight. The weight of a path is then the sum of weights of items associated with the edges on the path. For example, in the following figure, we have items of $I_1$, $I_2$, and $I_3$ with weights $w_1$, $w_2$, and $w_3$, respectively. The weight of paths $P_1$ and $P_2$ is computed as $w_1+w_2$ and $w_1+w_2+w_3$, respectively.

$w_{P_1}$ = $\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2, I_3\}~\cup~\{I_2\}~\}} w_\gamma$

$w_{P_2}$ = $\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2\}~\}} w_\gamma$

enter image description here

$\endgroup$
  • $\begingroup$ The follow-up question was discussed in this previous post (where it was observed to be as hard as set cover, and an incorrect approximation algorithm was suggested in an answer): cstheory.stackexchange.com/q/41026/8237 $\endgroup$ – Neal Young Jan 26 at 6:47
0
$\begingroup$

No, the natural generalization of Bellman-Ford to your setting won't necessarily converge to a correct solution.

Bellman-Ford proceeds in rounds. In each round it considers every edge (u, w), in round-robin fashion, and "relaxes" (u, w). In this setting, let's say that relaxing (u, w) does the following. As the algorithm proceeds, it maintains, for some vertices v, a path p[v] from s to v. Initially only p[s] is defined. To relax (u, w) does the following. If it has a path p[u] from s to u, it considers the path p' from s to w formed by p[u] followed by the edge (u, w). If that path p' is cheaper than p[w] (or p[w] is not defined), it sets p[w] to p'.

Here's a counter-example for such an algorithm, for the special case mentioned in your follow-up question.

The vertex set is V={s, a, b, c}. The edge set is E={(s, a), (a, b), (b, c), (s, b)}.

Edge (s, a) has item X of weight 2; (a, b) has no item; (b, c) has item X; (s, b) has item Y of weight 1.

The best path from s to b is (s, b) which uses item Y and has cost 1. But the best from s to c is (s, a, b, c), which uses item X and has cost 2.

In the first round of Bellman-Ford, the (shortest) path (s, b) to b will be discovered. After that, the path to b will remain (s, b) forever. So the path (s, a, b, c) to c, which requires the sub-path (s, a, b) to b, will never be discovered.

$\endgroup$
3
$\begingroup$

No, Bellman-Ford won't work because the problem you described is NP-hard.

This is pretty easy to prove. I've been able to come up with several reductions using the same strategy. The general idea is to make it so that in the path you have several sections that can be chosen independently; then the overall question becomes whether you can coordinate all those choices so as to minimize the sum of the weights of the items in the chosen subpaths. You can easily set up the independent choices by using a sequence of "bottleneck" vertices $S = v_0, v_1, \ldots, v_{n-1}, v_n=T$ and making several paths between each $v_i$ and $v_{i+1}$ (the choices of which path piece from $v_i$ to $v_{i+1}$ to take for each $i$ are the independent choices I was talking about earlier).

For example, you can reduce from 3SAT. For each variable $x$, make one of the subpath choices be between item $x$ and item $\neg x$. For each clause, make one of the choices be between the items corresponding to the literals in the clause. For each variable either the variable, the negation, or both must be in any path. The only way to get away with having only one version of each variable in the path is if there exists an assignment that makes every clause true. If each item has weight 1, then the overall weight of the items in the path will equal the number of variables iff the 3SAT instance is satisfiable.

As another example, you can reduce from set cover. For each set that you want to cover, make a piece of the path be a choice that lets you chose any of the items in that set. Then to minimize the number items chosen in all, you have to cover all the sets with as few items as possible.

$\endgroup$
  • $\begingroup$ Thank you so much for the answer! Would it be possible to approximate a solution using Bellman-Ford, that is, it wouldn't converge after $\vert V \vert -1$ iterations but would give me some solution? Also, can we prove that it will converge at some point? $\endgroup$ – mnmp Jan 25 at 4:38
  • $\begingroup$ Note that if you applied Bellman-Ford to any of the above examples, if it converged, it would have to converge in quadratically many steps, because the edge weights are all 1, and each step would decrease the cost of the current path to at least one vertex, which could happen at most n times per vertex. It follows that on the above examples Bellman-Ford must not converge (unless P=NP). Or, for a simpler counter-example to convergence, see the answer I just posted. $\endgroup$ – Neal Young Jan 26 at 5:30
  • $\begingroup$ The reduction from set cover in this answer is the same as in this answer to OP's previous post, and shows that the problem can't be approximated in poly-time any better than set cover, which in turn can't be approximated in poly-time by better than a log(n) factor (unless P=NP). $\endgroup$ – Neal Young Jan 26 at 6:48
  • $\begingroup$ Thank you for the followup and the helpful answers. $\endgroup$ – mnmp Jan 26 at 22:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.