Minimum Union-Sum Cost Path

Question

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?

Answer 1

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. $~~~\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:

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. (See here for a summary.)