Search code examples
algorithmreductionnpnp-completenp-hard

Proving NP-Completeness


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


Solution

  • 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