sys.'s blog

By sys., history, 6 months ago, ,

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)$

• +53

 » 6 months ago, # | ← Rev. 2 →   +25 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)$
•  » » 6 months ago, # ^ |   +14 You can submit this problem (where you minimize the difference) here.The constraints allow simpler approaches to get an "Accepted" verdict.
•  » » » 6 months ago, # ^ |   +6 Ohhhhh!Thank you!
 » 6 months ago, # |   -11 I bet you can solve the problem if N <= 10
•  » » 6 months ago, # ^ |   +9 ............That's for sure.
 » 6 months ago, # | ← Rev. 3 →   +77 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)$.
•  » » 6 months ago, # ^ | ← Rev. 4 →   +23 I'm sorry maybe you are right.
•  » » 6 months ago, # ^ |   +19 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.
•  » » 6 months ago, # ^ |   +20 $\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. CounterexampleOn the graph 5 4 1 5 0 2 3 1 3 4 2 4 2 3 the answer is clearly $0$, as there is exatly one path from $1$ to $5$, but $1 \to 5, 2 \to 3 \to 4 \to 2$ is a flow for the edges $1 - 5, 4 - 2$ giving you an answer of $3$.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.
 » 6 months ago, # |   0 Auto comment: topic has been updated by sysjuruo (previous revision, new revision, compare).
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 I think it's not right.But still thank you!
•  » » 6 months ago, # ^ |   +46 I think that you are trying to minimize the $|w_{max} - w_{min}|$. The problem asks that we should maximize the difference.
•  » » » 6 months ago, # ^ |   -13 Just change the weight segment then it becomes maximization.
•  » » » 6 months ago, # ^ |   0 Oh.....Maybe you are right.
•  » » 6 months ago, # ^ |   0 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?
 » 6 months ago, # |   0 Auto comment: topic has been updated by sysjuruo (previous revision, new revision, compare).
 » 6 months ago, # |   0 Auto comment: topic has been updated by sysjuruo (previous revision, new revision, compare).