Given $m$ shortest paths between any two vertices of an undirected graph. Determining whether we can pick $k$ shortest paths such that their union covers all edges.
I am trying to reduce set cover problem to it. For a set cover problem we can convert its elements into edges and the set represent a path from the first element to the last one. This conversion of set cover into a graph gives a tree kind of structure. Since between any two nodes in a tree the path is unique so, it has to be shortest as well. I formed a counter example of my own reduction which is given here. I believe that I am making some mistake somewhere but unable to recognize it.
Suppose you can solve this problem in polynomial time (in $k$ and $m$ and the size of the graph, say). Then, given an instance of set cover, name the elements of the universe $\{x_1,x_2,x_3,\ldots\,x_n\}$, and construct a graph with nodes $\{0,1,2,3,\ldots,n\} \cup \{x_1,\neg x_1, x_2, \neg x_2, \ldots, x_n,\neg x_n\}$ and edges from each $i$ to $x_{i+1}$ and $\neg x_{i+1}$ and from each $x_i$ or $\neg x_i$ to $i$. Then map the sets from the set cover problem onto shortest paths (from $0$ to $n$, of length $2n$) in the graph, and include an additional path corresponding to the empty set. Finding $k$ shortest paths such that their union includes all edges gives you a solution to the set cover problem: $k-1$ or $k$ sets (depending on whether you included the empty set) whose union is the universe. Conversely, if you can't find $k+1$ shortest paths whose union includes all edges, then there aren't $k$ sets whose union is the universe. The only wrinkle is the inclusion of the empty set, which wasn't necessarily in the original set cover problem.