2

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.

sv_jan5
  • 367
  • Cross-posted: http://cs.stackexchange.com/q/66751/755, http://math.stackexchange.com/q/1926535/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Dec 03 '16 at 05:20
  • Are you sure your problem is not in NP $\cap$ co-NP? Most situations I can think of where the answer is 'no' come with easy certificates, i.e. some edge that is not part of any of the $m$ shortest path you can choose from, or some max-flow min-cut like argument. What is an example where the answer is no but this is hard to verify? – Vincent Dec 06 '16 at 12:32
  • Are the edges of thos graph weighted? – kotomord Dec 07 '16 at 14:57
  • @kotomord yes you can assume it to be – sv_jan5 Dec 07 '16 at 14:58

1 Answers1

2

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.

mjqxxxx
  • 41,358
  • The problem statement says that graph has to be undirected in the shortest path problem but it seems to be that your reduction constructs a directed path. If possible also give a small example illustrating your procedure of reduction. – sv_jan5 Dec 07 '16 at 03:19