Minimum Union-Sum Cost Path
EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$, in which case the lemma claims that the algorithm will give an optimal solution.  The proof is wrong because the function $\Phi$ defined there is not supermodular.)  I do believe that the proof can be fixed, and the algorithm there can be patched, to obtain an $O(\log n)$-approximation algorithm.  I'll correct it  hopefully later this month. -NY



Your problem generalizes Set Cover, and in turn is a special case of the classical problem of minimizing a linear cost function subject to a submodular constraint, a problem for which the greedy Set-Cover algorithm and its logarithmic approximation ratio naturally extend (as observed e.g. by Wolsey in the 1980's).  Consequently, there is a poly-time log-approximation for your problem, and (unless P = NP) that is the best you can do. Here are the details.

Given any instance $I$ of your problem, define $N(I)$ to be the minimum, over all source-to-destination paths $p$, of the sum, over the edges $e$ in $p$, of the number of labels $F_i$ that $e$ has.  Unless P=NP, the best approximation-ratio obtainable for your problem is $\ln N(I)$ (up to lower-order terms). The reasoning is in two steps: a hardness result, then a poly-time $\ln N(I)$-approximation algorithm.



Here's the hardness result, showing that your problem subsumes Set Cover.

Lemma 1. Unless P=NP, the problem has no $((1-\epsilon)\ln N(I))$-approximation algorithm for any $\epsilon&gt;0$.

Proof. We give an approximation-preserving reduction from unweighted Set Cover.  Given an unweighted Set-Cover instance $(S_1, S_2, \ldots, S_m)$ on a universe $U=\{1,2,\ldots,n\}$, construct a multigraph with vertex set $\{1,\ldots,n,n+1\}$ where, for each element $i\in U$, for each set $S_j$ containing $i$, there is an edge $(i, i+1)$ with a single label $F_j$.  Set $C(F_j) = 1$ for each $j$.

(Note: If a multigraph is not allowed, one can simply split each $(i, i+1)$ with label $F_j$ into a path $(i, v(i,j), i+1)$ where $v(i,j)$ is a new vertex, edge $(i, v(i,j))$ has label $F_j$, and edge $(v(i,j), i+1)$ has no label...)

Then for any path $p$ from vertex $1$ to vertex $n+1$ there is a set cover $C(p) = \{S_j : F_j \text{ is the label of some edge on } p\}$ of size equal to the cost of $p$, and vice versa.  Also, $N(I)$ for this instance $I$ equals $n$.

So, if there is a $(1-\epsilon)\ln N(I)$-approximation algorithm for your problem, then there is a $(1-\epsilon)\ln n$-approximation algorithm for Set Cover.  Unless P=NP, there is no such algorithm. $~~~\Box$



EDIT: The remaining part is wrong, see comment at top.

Here's the upper bound, showing that your problem is a special case of minimizing a linear cost function subject to a submodular constraint.

Lemma 2. The problem has an $H_{N(I)}$-approximation algorithm, where $H_i \approx \gamma + \ln i$ is the $i$'th Harmonic number.

Proof. Fix an instance $I$ of the given problem. Assume without loss of generality that each edge in the graph has only one label.  (Otherwise, for any edge having, say, labels $F_{i_1}, F_{i_2},\ldots,F_{i_k}$, replace the edge by a path of $k$ edges, where the $j$th edge has label $F_{i_j}$.  This does not change $N(I)$.)

Given any set $S$ of labels, define $\phi(S)$ to be the minimum, over all paths $p$ from the source to the destination, of the number of edges on $p$ whose label is not in $S$.  Define the cost of $S$ to be the sum of the costs of the labels in $S$. Then 


$\phi$ is supermodular,  $\leftarrow$ EDIT: THIS IS NOT NECESSARILY TRUE
$\phi(\emptyset) = N(I)$,
$\phi(S) = 0$ if and only if there is a path from the source to the destination that uses only labels in $S$, and
the cost of $S$ is the cost of the labels in $S$.


Now apply Wolsey's generalization of the greedy-set-cover algorithm (for minimizing a linear function subject to a submodular constraint) to find an approximately minimum-cost set $S$ with $\phi(S) = 0$.  That algorithm is:


$S \leftarrow \emptyset$
while $\phi(S) &gt; 0$:
. . choose label $F_i$ maximizing
$\displaystyle\frac{\phi(S) - \phi(S\cup\{F_i\})}{C(F_i)}.$
. . add $F_i$ to $S$
return $S$


That algorithm is known to compute a solution $S$ of cost at most $H_D$ times the minimum, where $D = \max_{S,F_i} \{ \phi(S)-\phi(S\cup\{F_i\}) \le \phi(\emptyset) = N(I)$.

By inspection the algorithm can be implemented to run in polynomial time.

And, given the set $S$ with $\phi(S)=0$, one can easily compute in poly-time a path $p$ from the source to the destination with cost at most the cost of $S$.  $~~\Box$



Did I miss anything here?

Wolsey's original paper:

[1] L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982. (See here for a summary.)