Finding survivable paths with a set of vulnerable edges

Question

Consider a graph $G=(V,E)$ and a source-destination pair $(s,t)$. A set of edges $E'\subseteq E$ are vulnerable in the sense that at most $k$ of them may fail. My problem is to find a set of $(s,t)$ paths of minimum total cost such that no matter which subset of $k$ edges in $E'$ fail, we can ensure that there exist at least a functional $(s,t)$ path. My questions are: (1) Is this problem NP-hard? (2) If yes, how to design approximation algorithm?

Answer 1

For $(i,j)\in A$, let $c_{ij}$ be the arc cost. Let $P$ be the set of all $(s,t)$ paths. Let binary decision variable $\lambda_p$ indicate whether path $p\in P$ is selected, with arc set $A_p$ and cost $c(P) = \sum_{(i,j)\in A_p} c_{ij}$. The problem is to minimize $$\sum_{p\in P} c(P) \lambda_p \tag0\label0$$ subject to \begin{align} \sum_{p\in P: A_p \cap S = \emptyset} \lambda_p &\ge 1 &&\text{for all $S\subseteq E'$ such that $|S|\le k$} \tag1\label1\\ \lambda_p &\in\{0,1\} &&\text{for all $p\in P$} \tag2\label2 \end{align} Equivalently, you can replace $|S|\le k$ with $|S|=k$ in \eqref{1} and relax \eqref{2} to $\lambda_p \in \mathbb{Z}^+$.

There are an exponential number of variables, so you might use column generation to solve the problem exactly.

I suspect that you can demonstrate NP-hardness by reduction from weighted set cover. In any case, this problem is a special case of weighted set cover, so you can use any approximation algorithms for that problem, such as https://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm.