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?