Bellman-Ford with Non-edge-decomposable Path Weights

Question

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$

Answer 1

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 2

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.