Minimizing distance on a graph by adding shortcuts

Question

Hello,

I know next to nothing about graph theory, but in my work I have encountered an application for which I would like to do the following: Given a connected graph $G$ and integer $k > 0$, add a set of $k$ edges ("shortcuts") to $G$ to minimize the average "travel" distance on $G$ between vertices. Here, every edge has equal weight. I do not desire a provably minimal solution, but I would rather accept a slightly sub-optimal set of shortcuts if it meant that I could greatly lower the computation time.

A quick Google search yields two interesting papers, http://www.cs.ucla.edu/~awm/papers/APPROX09-NoC.pdf and dspace.mit.edu/openaccess-disseminate/1721.1/62215, one of which addresses my problem directly and another that tackles a related problem (minimizing diameter).

However, because I know little about graph theory, I was wondering if there might be other papers that I might find, or even textbook references, if there are any special cases for which this problem is significantly easier (as the graph I have is far from typical, and I suspect it has some nice properties).

Answer 1

Let's look at what happens when you add an edge to a connected (simple, undirected and incomplete) graph G.

Let $N_d(v)$ denote that subset of the vertices of G that are a distance precisely $d$ (i.e. shortest path in G has $d$ edges) from the vertex $v$ belonging to G. If $v$ and $w$ are a distance $c$ apart, then for suitably small $d$ and $f$, say each less than $c/4$, the distance between a point in $N_d(w)$ and one in $N_f(v)$ will (upon adding an edge between $v$ and $w$, and say $c>4$) go down from some number larger than $c/2$ to $1+d+f$. The reduction in total distances will be greater not only as $c$ increases but also from judicious selection of $v$ and $w$ so that the sets involved ($N_d(w)$ and $N_f(v)$ for small values of $f$ and $d$) are made larger.

It may be computationally intensive to compute sizes of the sets $N_d(v)$, so as a rough measure, try instead $d=1$, which gives the degree of $v$, which may be reasonable to compute for a fraction of the vertices. If your graph is nicely sparse, you may get away with adding k edges to the k most remote pairs among a set of 2k vertices with high and preferably maximal degree. This heuristic can perform badly on graphs with one or two large cliques, depending on their placement. Also, you might have as a side constraint to keep the maximal degree low, so don't add too many edges to the same vertex in this case.

Gerhard "Ask Me About System Design" Paseman, 2011.09.30

Answer 2

Connect the two vertices that correspond to the largest (most positive) and the smallest (most negative) values of the Fiedler vector.