Given m shortest paths between any two vertices of a graph. Determining whether we can pick k shortest paths such that their union covers all edges.
I am sure that reduction has to be from set cover but I am not getting a way how to reduce it to this problem. Please help me with it
Hint: look at the graph below. There are lots of different shortest paths from A to B. Can you encode set cover using a graph like this and a set of paths? (well, you will probably have to modify the graph a bit, but this is the general idea).
o o o o o o o o o o o o o
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
A o o o o o o o o o o o o B
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
o o o o o o o o o o o o o