Блог пользователя yunoac

Minimum edges to delete to make shortest paths intersect
Автор yunoac, история, 8 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Property 1.

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

    → Ответить