Lexicographic perturbation for euclidean shortest path instances?

Question

Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such that the following statements hold:

1. For every pair $s\neq t \in V$, there is a unique shortest s-t-path $P_{s,t}$ in $G$ w.r.t. the euclidean weight function $c(v,w)=|\pi'(v)-\pi'(w)|_2$.

2. $P_{s,t}$ is also a shortest s-t-path w.r.t. the original vertex positions $\pi$.

3. $\pi'$ can be deterministically computed in polynomial time given $\pi$. The length of the numbers occuring in $\pi'$ are polynomially bounded in the length of those in $\pi$.

I know that lexicographic perturbation is a standard procedure to do this deterministically. Sadly there is no simple way to modify the distance of only a single edge in euclidean instances.

Is there any known approach that can be applied to those euclidean instances? Even a randomized perturbation algorithm would be interesting for me.

Answer 1

I think you're unlikely to get a good answer, because this is tied up in difficult and unsolved algebraic problems. The issue is that Euclidean path lengths (for points with integer coordinates) can be expressed as sums of square roots, but we don't know how small the difference between two distinct sums of square roots can be. Because of this, we also don't know how far apart the shortest path length and second-shortest distinct path length between a given pair of vertices can be, and therefore we don't know how small we have to make a perturbation to prevent it from changing the shortest path to a path that wasn't originally shortest.

For the same reason, shortest paths in Euclidean graphs are not really known to be solvable in polynomial time, in models of computation that take into account the bit complexity of the inputs, even though Dijkstra is polynomial in a model of computation allowing constant-time real-number arithmetic. So asking for a polynomial time algorithm for a more complicated variant of the problem in which the bit complexity is unavoidable seems likely to have a negative answer.