Minimum edges to delete to make shortest paths intersect

Revision en1, by yunoac, 2017-05-09 08:31:11

On my research I came across the following problem.

Given a weighted graph G = (V,E,w) and four nodes s1,t1,s2,t2 find the minimum number of edges that need to be deleted from G so that the set of shortest paths from s1 to t1 and the set of shortest paths from s2 to t2have at least one edge in common.

I have been trying to prove that this problem is NP-hard but I was not able to come up with anything. Does anyone have any idea?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English yunoac 2017-05-09 08:36:51 1 Tiny change: 'm s2 to t2have at le' -> 'm s2 to t2 have at le'
en1 English yunoac 2017-05-09 08:31:11 494 Initial revision (published)