Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$.

You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points. That is, every vertex $v$ corresponds to some point $(x,y)$ in the plane, and for an edge $(u,v)=((x_1,y_1),(x_2,y_2))$ its weight is equal to $\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

  • 2
    $\begingroup$ Take two cliques connected by a path with two edges. Adding one edge directly between the cliques shortens $\Omega(n^2)$ of the shortest paths. $\endgroup$
    – Louis
    Apr 5, 2012 at 19:30
  • 1
    $\begingroup$ @Louis: yes, there are examples in which a single edge causes a lot of distances to change, but do there exist graphs in which that happens for every edge you add, or at least for a lot of them? This is exactly why I defined $C$ to be the average over all edges :) $\endgroup$ Apr 5, 2012 at 19:37
  • 1
    $\begingroup$ Most of the edges in this graph that can be added are of the type I described... $\endgroup$
    – Louis
    Apr 5, 2012 at 19:42
  • $\begingroup$ @Louis True. Cliques contain $O(n^2)$ edges though, which is more than I will ever add to my graph. $\endgroup$ Apr 5, 2012 at 19:48
  • $\begingroup$ I had a same problem before, but My graph was kind of sparse graphs with $|E|=O(|V|)$ and I should to prove average changes is O(1) but I couldn't do so :-). But for your case I think if you find a relation between this and solution of APSP you can get some results. $\endgroup$
    – user742
    Apr 5, 2012 at 20:46

1 Answer 1


Consider the following linear chain with $n+1$ nodes, $n$ edges and viciously chosen weights:


Clearly, the edges could have been added in order of their weights and there are $n \in \mathcal{O}(|V|)$ of them. Adding the dashed edge (which is legal) creates shorter paths for all pairs $(u_i,b_j)$ with $i,j = 1,\dots,k$. As $k \approx \frac{n}{4}$ and assuming that $n \in \Theta(|V|)$, both first and last row contain $\Theta(|V|)$ many nodes each and the addition causes $\Theta(|V|^2)$ many shortest path changes.

We can now move "outwards" now, i.e. add the next edge with weight $n+2$ between $u_{k-1}$ and $b_{k-1}$ and so on; if we continue this to $(u_1,b_1)$, we cause in total $\Theta(|V|^3)$ shortest path changes.

If this does not convince you, note that you can actually start this "process" with $(c_1,c_2)$ and work outwards from there; this way you add $\approx n$ edges which cause in total $\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$ many shortest path changes---this is just impossible to draw to fit on one screen.

  • 1
    $\begingroup$ This indeed works, and furthermore, your example can be changed a bit to become Euclidian. Thanks :) $\endgroup$ Apr 6, 2012 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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