<p>EDIT (Jan 2019): <em>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 <span class="math-container">$N(I)=1$</span>, in which case the lemma claims that the algorithm will give an optimal solution.  The proof is wrong because the function <span class="math-container">$\Phi$</span> defined there is not supermodular.)  I do believe that the proof can be fixed, and the algorithm there can be patched, to obtain an <span class="math-container">$O(\log n)$</span>-approximation algorithm.  I'll correct it  hopefully later this month. -NY</em></p>

<hr>

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

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

<hr>

<p>Here's the hardness result, showing that your problem subsumes Set Cover.</p>

<p><strong>Lemma 1.</strong> <em>Unless P=NP, the problem has no <span class="math-container">$((1-\epsilon)\ln N(I))$</span>-approximation algorithm for any <span class="math-container">$\epsilon&gt;0$</span>.</em></p>

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

<p>(Note: If a multigraph is not allowed, one can simply split each <span class="math-container">$(i, i+1)$</span> with label <span class="math-container">$F_j$</span> into a path <span class="math-container">$(i, v(i,j), i+1)$</span> where <span class="math-container">$v(i,j)$</span> is a new vertex, edge <span class="math-container">$(i, v(i,j))$</span> has label <span class="math-container">$F_j$</span>, and edge <span class="math-container">$(v(i,j), i+1)$</span> has no label...)</p>

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

<p>So, if there is a <span class="math-container">$(1-\epsilon)\ln N(I)$</span>-approximation algorithm for your problem, then there is a <span class="math-container">$(1-\epsilon)\ln n$</span>-approximation algorithm for Set Cover.  Unless P=NP, <a href="https://en.wikipedia.org/wiki/Set_cover_problem#Inapproximability_results" rel="nofollow noreferrer">there is no such algorithm</a>. <span class="math-container">$~~~\Box$</span></p>

<hr>

<p>EDIT: <em>The remaining part is wrong, see comment at top</em>.</p>

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

<p><strong>Lemma 2.</strong> <em>The problem has an <span class="math-container">$H_{N(I)}$</span>-approximation algorithm, where <span class="math-container">$H_i \approx \gamma + \ln i$</span> is the <span class="math-container">$i$</span>'th Harmonic number.</em></p>

<p><em>Proof.</em> Fix an instance <span class="math-container">$I$</span> 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 <span class="math-container">$F_{i_1}, F_{i_2},\ldots,F_{i_k}$</span>, replace the edge by a path of <span class="math-container">$k$</span> edges, where the <span class="math-container">$j$</span>th edge has label <span class="math-container">$F_{i_j}$</span>.  This does not change <span class="math-container">$N(I)$</span>.)</p>

<p>Given any set <span class="math-container">$S$</span> of labels, define <span class="math-container">$\phi(S)$</span> to be the minimum, over all paths <span class="math-container">$p$</span> from the source to the destination, of the number of edges on <span class="math-container">$p$</span> whose label is not in <span class="math-container">$S$</span>.  Define the <em>cost</em> of <span class="math-container">$S$</span> to be the sum of the costs of the labels in <span class="math-container">$S$</span>. Then </p>

<ul>
<li><span class="math-container">$\phi$</span> is supermodular,  <em><span class="math-container">$\leftarrow$</span> EDIT: THIS IS NOT NECESSARILY TRUE</em></li>
<li><span class="math-container">$\phi(\emptyset) = N(I)$</span>,</li>
<li><span class="math-container">$\phi(S) = 0$</span> if and only if there is a path from the source to the destination that uses only labels in <span class="math-container">$S$</span>, and</li>
<li>the cost of <span class="math-container">$S$</span> is the cost of the labels in <span class="math-container">$S$</span>.</li>
</ul>

<p>Now apply <a href="http://algnotes.info/on/background/set-cover-wolsey/" rel="nofollow noreferrer">Wolsey's generalization</a> of the greedy-set-cover algorithm (for <em>minimizing a linear function subject to a submodular constraint</em>) to find an approximately minimum-cost set <span class="math-container">$S$</span> with <span class="math-container">$\phi(S) = 0$</span>.  That algorithm is:</p>

<ol>
<li><span class="math-container">$S \leftarrow \emptyset$</span></li>
<li><p>while <span class="math-container">$\phi(S) &gt; 0$</span>:</p></li>
<li><p>. . choose label <span class="math-container">$F_i$</span> maximizing
<span class="math-container">$\displaystyle\frac{\phi(S) - \phi(S\cup\{F_i\})}{C(F_i)}.$</span></p></li>
<li>. . add <span class="math-container">$F_i$</span> to <span class="math-container">$S$</span></li>
<li>return <span class="math-container">$S$</span></li>
</ol>

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

<p>By inspection the algorithm can be implemented to run in polynomial time.</p>

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

<hr>

<p>Did I miss anything here?</p>

<p>Wolsey's original paper:</p>

<p>[1] <a href="http://scholar.google.com/scholar?q=author:%22L+Wolsey%22+intitle:%22+An+analysis+of+the+greedy+algorithm+for+the+submodular+set+covering+problem" rel="nofollow noreferrer">L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982.</a> (See <a href="http://algnotes.info/on/background/set-cover-wolsey/" rel="nofollow noreferrer">here</a> for a summary.)</p>

CC BY-SA 4.0
2018-06-27T03:45:51.643Z
2019-01-26T07:12:34.450Z
2019-01-26T07:12:34.450Z
Neal Young
<p>I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path have that type of cost. For example, in the example below, cost of the red path that goes from S to D is C(F1)+C(F2). Although both F1 and F2 appear multiple times along the path, each one of them is only counted once. This path also is the minimum cost path since any other path will have F3 as well and so its cost will be C(F1)+C(F2)+C(F3). Costs are positive real numbers and are known for each item.</p>

<p>I named it Union-Sum Cost since if we look at different edges, cost of a path is the sum of costs of the union of items associated with the edges on the path.</p>

<p>Has this problem been solved before? (like an approximation algorithm) Is there a well-known graph problem that resembles this? And do you think this is a hard problem?</p>

<p><a href="https://i.sstatic.net/JBScT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/JBScT.png" alt="Minimum Union-Sum Cost Path"></a></p>

CC BY-SA 4.0
2018-06-19T06:42:41.807Z
Are the costs C(F1), C(F2), C(F3) provided as inputs?
D.W.
CC BY-SA 4.0
2018-06-19T06:45:11.133Z
Are the costs guaranteed to be non-negative?  Can they be negative?
D.W.
CC BY-SA 4.0
2018-06-19T07:34:26.353Z
Yes and yes. Costs are positive and given.
mnmp
CC BY-SA 4.0
2018-06-26T02:19:31.473Z
@NealYoung Thanks for the comment. The problem with assigning weights to edges is that we cannot use such weights later as we need to compute the union of items associated with edges on any path **p** from **s** to **t**. The way I understand it, assigning weights to edges does not solve the problem.
mnmp
CC BY-SA 4.0
2018-06-27T02:02:39.207Z
Thanks @NealYoung. But the way you defined it set F1 alone should be enough to create a path and we wouldn't need F2. Also, I don't think this is an exact representation of set cover as we are not trying to cover a specific path from s to t.
mnmp
CC BY-SA 4.0
2018-06-27T03:47:36.727Z
You're right, my answer wasn't quite right.  I was assuming there was only one label per edge.  I've deleted my incorrect comments above.  I've (hopefully) fixed the idea.  I've posted the details in the answer below.
Neal Young
<graph-theory><graph-algorithms><optimization><integer-programming><shortest-path>
Minimum Union-Sum Cost Path
mnmp
# Minimum Union-Sum Cost Path

(Asked by: username_0 on 2018-06-19)

I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path have that type of cost. For example, in the example below, cost of the red path that goes from S to D is C(F1)+C(F2). Although both F1 and F2 appear multiple times along the path, each one of them is only counted once. This path also is the minimum cost path since any other path will have F3 as well and so its cost will be C(F1)+C(F2)+C(F3). Costs are positive real numbers and are known for each item.

I named it Union-Sum Cost since if we look at different edges, cost of a path is the sum of costs of the union of items associated with the edges on the path.

Has this problem been solved before? (like an approximation algorithm) Is there a well-known graph problem that resembles this? And do you think this is a hard problem?

[![Minimum Union-Sum Cost Path](https://i.sstatic.net/JBScT.png)](https://i.sstatic.net/JBScT.png)

**Tags:** graph-theory, graph-algorithms, optimization, integer-programming, shortest-path

> **Comments:**
> **username_1**: Are the costs C(F1), C(F2), C(F3) provided as inputs?  
> **username_1**: Are the costs guaranteed to be non-negative?  Can they be negative?  
> **username_0**: Yes and yes. Costs are positive and given.  
> **username_0**: @NealYoung Thanks for the comment. The problem with assigning weights to edges is that we cannot use such weights later as we need to compute the union of items associated with edges on any path **p** from **s** to **t**. The way I understand it, assigning weights to edges does not solve the problem.  
> **username_0**: Thanks @NealYoung. But the way you defined it set F1 alone should be enough to create a path and we wouldn't need F2. Also, I don't think this is an exact representation of set cover as we are not trying to cover a specific path from s to t.  
> **username_2**: You're right, my answer wasn't quite right.  I was assuming there was only one label per edge.  I've deleted my incorrect comments above.  I've (hopefully) fixed the idea.  I've posted the details in the answer below.  

---

## 1 answers

### Answer by username_2 on 2018-06-27. Score: 3 | Accepted answer

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>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](https://en.wikipedia.org/wiki/Set_cover_problem#Inapproximability_results). $~~~\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](http://algnotes.info/on/background/set-cover-wolsey/) 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:

1. $S \leftarrow \emptyset$
2. while $\phi(S) > 0$:
3. . . choose label $F\_i$ maximizing
   $\displaystyle\frac{\phi(S) - \phi(S\cup\{F\_i\})}{C(F\_i)}.$
4. . . add $F\_i$ to $S$
5. 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.](http://scholar.google.com/scholar?q=author:%22L+Wolsey%22+intitle:%22+An+analysis+of+the+greedy+algorithm+for+the+submodular+set+covering+problem) (See [here](http://algnotes.info/on/background/set-cover-wolsey/) for a summary.)


---

