sys.'s blog

A problem I can't solve
By sys., history, 5 years ago, In English

One day when I had my math class,I came up with an idea.But I found that I can't solve it.

After class I asked many people but they did't solve it too.

Here's the problem:

You are given a undirected weighted graph with n nodes and m edges.

You need to find a simple path from 1 to n to maximize the maximum value of edges in the path minus the minimum one.

A simple path means that you can't pass through one edge twice or more.

(I don't know how large n,m can be)

Update:Thanks to TimonKnigge,we can solve it in $$$O(m^2 \times n^3)$$$

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

»
5 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

If the problem is minimize the maximum value of edges in the path minus the minimum one.

we can use Link-Cut Tree and two pointer to solve it.

We can sort edges by their value and add it in the Link-Cut Tree.

If there is a loop,we can delete the edge which has the minimum value in the loop.

The complexity is $$$O(mlogm)$$$

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

    You can submit this problem (where you minimize the difference) here.

    The constraints allow simpler approaches to get an "Accepted" verdict.

    → Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I bet you can solve the problem if N <= 10

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

    ............

    That's for sure.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +77 Vote: I do not like it

A slow but polynomial solution: let's loop over all $$$O(m^2)$$$ pairs of candidate edges for the minimum and maximum edge. Remove all edges that have smaller or larger weight. Now we want to find a simple path from $$$1$$$ to $$$n$$$ in the remaining graph that uses these two edges. However, this is a relatively straightforward flow problem. We simply set the minimum capacity of these two edges to $$$1$$$ (and the maximum capacity of all edges to $$$1$$$ as well) and find a flow from $$$1$$$ to $$$n$$$. It is pretty easy to see the number of augmenting paths for this problem will be constant, so the complexity is $$$O(m^3)$$$.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +23 Vote: I do not like it

    I'm sorry maybe you are right.

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

    Remove all edges that have smaller or larger weight.

    We don't even need this, since we're looking for the maximum difference. That means we can work with a fixed graph, but idk if it improves things.

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

    $$$\def\set[#1]{\left\{#1\right\}}$$$

    The flow might have some cycles disjoint from the path from $$$1$$$ to $$$n$$$, so you won't necessaritly find a simple path.

    Counterexample

    Instead, loop over all pairs $$$(e_1, e_2)$$$ of edges. A simple path from $$$1$$$ to $$$n$$$ that uses two edges $$$e_1 = \set[u_1, v_1]$$$,$$$ e_2 = \set[u_2, v_2]$$$ looks like

    $$$ 1 -\dots -u_1 -v_1 -\dots -u_2 -v_2 -\dots -n $$$

    up to some permutation of $$$\set[u_1, v_1, u_2, v_2]$$$, so the problem of finding such a path boils down to finding three vertex disjoint paths $$$1 - \dots - u_1, v_1 - \dots - u_2, v_2 - \dots - n$$$. The paper Graph Minors .XIII. The Disjoint Paths Problem gives a (complicated) $$$O(n^3)$$$ algorithm for checking if such paths exist, so we get $$$O(m^2 n^3)$$$ runtime in total.

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

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

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

I think it can be solved faster. Let's do binary search of the answer. Now, we want to check whether we can reach difference less than $$$d$$$. If we fix maximum weight $$$w_{max}$$$ that will present in the path it's easy to see that all available weights of edges from a segment $$$[w_{max}-d, w_{max}]$$$. So we got a solution that works in $$$O(m^2 \cdot log(MAX \underline\ W))$$$.

From the other point of view all edges are available in segment of maximal weights in the path so we can apply dynamic connectivity over the weights, where every edge available in $$$[w, w+d]$$$. We got something about $$$O(m \cdot log(m) \cdot log(MAX \underline\ W))$$$.

Correct me if I'm wrong.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think it's not right.But still thank you!

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

    I think that you are trying to minimize the $$$|w_{max} - w_{min}|$$$. The problem asks that we should maximize the difference.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Just change the weight segment then it becomes maximization.

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

      Oh.....Maybe you are right.

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

    Say you have a direct edge from $$$1$$$ to $$$n$$$ of some weight $$$w$$$ (amongst other edges). How does your algorithm work in this case?

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

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

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

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

→ Reply