Shortest paths perturbation

Question

I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that there is a path from $u$ to $v$, there is, after perturbation, a unique shortest path from $u$ to $v$, and this shortest path is one of the "original" shortest paths, that is, one of the shortest paths before the perturbation. It seems to me that the perturbation can only be additive and at most equal to the minimum difference between two edge weights divided by the maximum number of vertices in a shortest paths between pair of vertices in $G$ (let this number be $\Delta$). That is, the perturbation that I add to the edge $e\in E$ should be some $$ \varepsilon_e \in\left[0, \frac{\min_{\ell,r\in E}|w_\ell-w_r|}{\Delta}\right] $$ and distributed according to some distribution (is uniform sufficient?) on the interval.

Possibly, I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible? Any reference or hint is appreciated. Thanks.

Answer 1

Probably the simplest approach is to perturb the edge weights symbolically rather than numerically. Intuitively, you'd like to reassign the weight of each edge as $$ \tilde{w}(e) = w(e) + \varepsilon \cdot w'(e) $$ where $w(e)$ is the original edge weight, $w'(e)$ is a secondary edge weight, and $\varepsilon$ is a global scaling factor. This perturbation scheme has to satisfy two requirements:

• Every shortest path with respect to the perturbed edge weights must be also a shortest path with respect to the original edge weights. It's not hard to prove that for any function $w'$, this property holds for all sufficiently small scaling factors $\varepsilon$. Rather than spending time figuring out how small "sufficiently small" is, consider instead the limiting behavior as $\varepsilon$ approaches $0$. Then your perturbed edge weights are best formalized as two-dimensional vectors $$ \tilde{w}(e) = \big( w(e), w'(e) \big). $$ The length of any path is also a vector, obtained by summing the vector-weights of each edge on the path. Comparisons between length vectors are performed lexicographically: $$ (a, a') < (b, b') \iff a<b \text{ or } (a = b \text{ and } a'<b') $$ This definition trivially implies that for any paths $\alpha$ and $\beta$, if $w(\alpha) < w(\beta)$, then $\tilde{w}(\alpha) < \tilde{w}(\beta)$. One nice feature of this scheme is that if shortest paths with respect to $w$ are already unique, the algorithm never even notices $w'$.

• Shortest paths with respect to the perturbed edge weights must be unique. It suffices to choose a function $w'$ such that shortest paths with respect to $w'$ are unique. There are two standard methods for finding such a function $w'$.

  1. The simplest method is to generate each $w'(e)$ randomly. The Isolation Lemma of Mulmuley, Vazirani, and Vazirani implies that if each $w'(e)$ is chosen independently and uniformly at random from the set $\{1, 2, \dots, n^4\}$, then with probability $1-O(1/n)$, all shortest paths are unique. This scheme works for any shortest path algorithm with no run-time penalty and little modification to the algorithm, but it does have a small probability of failure.

  2. A more complex deterministic method (which linear-programming people know as "lexicographic perturbation") indexes the edges from $1$ to $m$ and defines $w'(e_i) = 2^i$. Clearly every subset of edges has distinct total $w'$eight. However, using this method requires manipulating $m$-bit integers, so it's more efficient to implement this method symbolically as well. For any paths $\alpha$ and $\beta$, we have $w'(\alpha) < w'(\beta)$ if and only if the minimum edge-index in $\alpha\setminus\beta$ is smaller than the minimum edge-index in $\beta\setminus\alpha$. Most shortest-path algorithms only compare paths that share a common prefix (starting at some source node $s$) and are otherwise edge-disjoint. With an appropriate dynamic tree data structure (e.g., link-cut trees or top trees), it is possible to find the node where the two paths split and the minimum edge-index along the disjoint suffixes in $O(\log n)$ amortized time. So, this scheme is always correct, but it imposes a penalty in the running time that is only $O(\log n)$ if your algorithm has the right structure, and it requires significant data structure overhead.

You can guess which method I recommend. My recent journal paper with Sergio Cabello and Erin Chambers describes both of these perturbation schemes in more detail.

There are also more specialized methods for specific algorithms and specific classes of graphs.

I would also like the "perturbed" shortest path to be chosen uniformly at random from the set of original shortest paths. Is this possible?

I don't know. In particular, the randomized perturbation scheme I described does not have this property.