<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-06-28T18:01:20.617Z
Thank you, this answer actually makes a lot of sense. Is there some overview article that lists these open problems for euclidean weight functions?
Listing
CC BY-SA 3.0
2015-06-28T18:29:11.410Z
I think http://cs.smith.edu/~orourke/TOPP/P33.html is a pretty good overview.
David Eppstein
CC BY-SA 3.0
2015-06-28T17:43:05.630Z
2015-06-28T17:43:05.630Z
David Eppstein
<p>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:</p>

<ol>
<li><p>For every pair $s\neq t \in V$, there is a <strong>unique</strong> shortest s-t-path $P_{s,t}$ in $G$ w.r.t. the euclidean weight function $c(v,w)=|\pi'(v)-\pi'(w)|_2$.</p></li>
<li><p>$P_{s,t}$ is also a shortest s-t-path w.r.t. the original vertex positions $\pi$.</p></li>
<li><p>$\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$.</p></li>
</ol>

<p>I know that <a href="https://cstheory.stackexchange.com/a/17581/13956">lexicographic perturbation</a> 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.</p>

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

<reference-request><graph-theory>
Lexicographic perturbation for euclidean shortest path instances?
Listing
# Lexicographic perturbation for euclidean shortest path instances?

(Asked by: username_0 on 2015-06-28)

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](https://cstheory.stackexchange.com/a/17581/13956) 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.

**Tags:** reference-request, graph-theory


---

## 1 answers

### Answer by username_1 on 2015-06-28. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you, this answer actually makes a lot of sense. Is there some overview article that lists these open problems for euclidean weight functions?  
> **username_1**: I think http://cs.smith.edu/~orourke/TOPP/P33.html is a pretty good overview.  

---

