Adibov's blog

An interesting question

By Adibov, history, 6 years ago, In English

I was thinking on a problem and i figure out an interesting problem that i can't solve it so could you help me?

We have an undirected weighted graph and Q queries. Each query has two vertices u and v. For each query erase all of edges between one of the path from v to u, so that sum of all weight of edges that has been erased from all queries become maximized.

I have no idea about time complexity, so there is no limit for n and Q. And if you have seen this problem before please give me the URL.

Thanks. :)

UPD : We want that sum of all queries become minimized.

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

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Actually the problem is equal to longest path when all weights are 1 and Q = 1. So it's np-hard!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you but what if we want that sum of all queries become minimized?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That can be solved with min-cost flow.

      Add two new nodes, a source and a sink. Set cost of all edges to 1, then add edges from source to startpoints of the queries, and add edges from endpoints of the queries to the sink. Then minimize cost when pushing Q units of flow.

      I doubt there's anything much faster than this.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Adibov (previous revision, new revision, compare).

→ Reply