yunoac's blog

Minimum edges to delete to make shortest paths intersect
By yunoac, history, 7 years ago, In English

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?

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Would you mind clarifying the problem a little? Which of the following two properties do you want to be held in the resulting subgraph:

  1. There is a shortest path from s1 to t1 and a shortest path from s2 to t2 such that they have at least one edge in common.
  2. Any pair of shortest paths from s1 to t1 and from s2 to t2 has at least one edge in common.

Also, is the graph directed or not?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Property 1.

    Undirected. But I am interested in both cases. So if you have an idea for any of them please let me know.

    → Reply