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 t2 have 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?
Would you mind clarifying the problem a little? Which of the following two properties do you want to be held in the resulting subgraph:
Also, is the graph directed or not?
Property 1.
Undirected. But I am interested in both cases. So if you have an idea for any of them please let me know.