6
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, this answer actually makes a lot of sense. Is there some overview article that lists these open problems for euclidean weight functions? $\endgroup$ – Listing Jun 28 '15 at 18:01
  • 2
    $\begingroup$ I think cs.smith.edu/~orourke/TOPP/P33.html is a pretty good overview. $\endgroup$ – David Eppstein Jun 28 '15 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.