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

<p>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'.</p>

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

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

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-01-26T04:54:30.163Z
2019-01-26T04:54:30.163Z
Neal Young
<p>No, Bellman-Ford won't work because the problem you described is NP-hard.</p>

<p>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 <span class="math-container">$S = v_0, v_1, \ldots, v_{n-1}, v_n=T$</span> and making several paths between each <span class="math-container">$v_i$</span> and <span class="math-container">$v_{i+1}$</span> (the choices of which path piece from <span class="math-container">$v_i$</span> to <span class="math-container">$v_{i+1}$</span> to take for each <span class="math-container">$i$</span> are the independent choices I was talking about earlier).</p>

<p>For example, you can reduce from 3SAT. For each variable <span class="math-container">$x$</span>, make one of the subpath choices be between item <span class="math-container">$x$</span> and item <span class="math-container">$\neg x$</span>. 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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-01-25T04:38:44.050Z
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?
mnmp
CC BY-SA 4.0
2019-01-26T05:30:10.867Z
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.
Neal Young
CC BY-SA 4.0
2019-01-26T06:48:22.013Z
The reduction from set cover in this answer is the same as in [this answer](https://cstheory.stackexchange.com/a/41097/8237) 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).
Neal Young
CC BY-SA 4.0
2019-01-26T22:17:49.020Z
Thank you for the followup and the helpful answers.
mnmp
CC BY-SA 4.0
2019-01-25T04:20:42.480Z
2019-01-25T04:20:42.480Z
Mikhail Rudoy
<p>Consider a directed graph <span class="math-container">$G(V,E)$</span> 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 <span class="math-container">$S$</span> to some sink <span class="math-container">$T$</span> after some number of iterations? Would Bellman-Ford converge eventually?</p>

<p>Follow up question:</p>

<p>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 <span class="math-container">$I_1$</span>, <span class="math-container">$I_2$</span>, and <span class="math-container">$I_3$</span> with weights <span class="math-container">$w_1$</span>, <span class="math-container">$w_2$</span>, and <span class="math-container">$w_3$</span>, respectively. The weight of paths <span class="math-container">$P_1$</span> and <span class="math-container">$P_2$</span> is computed as <span class="math-container">$w_1+w_2$</span> and <span class="math-container">$w_1+w_2+w_3$</span>, respectively.</p>

<p><span class="math-container">$w_{P_1}$</span> = <span class="math-container">$\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2, I_3\}~\cup~\{I_2\}~\}} w_\gamma$</span></p>

<p><span class="math-container">$w_{P_2}$</span> = <span class="math-container">$\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2\}~\}} w_\gamma$</span></p>

<p><a href="https://i.sstatic.net/4sQXS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4sQXS.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2019-01-26T06:47:30.907Z
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): https://cstheory.stackexchange.com/q/41026/8237
Neal Young
<optimization><shortest-path>
Bellman-Ford with Non-edge-decomposable Path Weights
mnmp
# Bellman-Ford with Non-edge-decomposable Path Weights

(Asked by: username_0 on 2019-01-24)

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](https://i.sstatic.net/4sQXS.png)](https://i.sstatic.net/4sQXS.png)

**Tags:** optimization, shortest-path

> **Comments:**
> **username_1**: 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): https://cstheory.stackexchange.com/q/41026/8237  

---

## 2 answers

### Answer by username_1 on 2019-01-26. Score: 0 | Accepted answer

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.


---

### Answer by username_2 on 2019-01-25. Score: 3

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_1**: The reduction from set cover in this answer is the same as in [this answer](https://cstheory.stackexchange.com/a/41097/8237) 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).  
> **username_0**: Thank you for the followup and the helpful answers.  

---

