My problem is to find places to put k number of shortcut edges with weight 0 to minimize maximum distance in grid graph where all edges are weighted 1! I found a related topic to my question Minimizing distance on a graph by adding shortcuts but similar to Christopher I don't understand many mathematical concepts.

I've tried to analyze Paper that Christopher found but still don't know how could I implement this to my problem! Trying to be more specified let's look at grid graph:

Grid graph

I want to add k shortcut edges to minimize maximum distance. Example:

Grid graph with shortcuts

So the question in what is the which nodes to connect, and how to prove that this is the best solution!


It's not hard to bound the new distance to within a constant factor, as a function of $k$. If you add $k$ shortcut edges to an $n\times n$ grid, the number of points within distance $d$ of an endpoint of a shortcut will be $O(kd^2)$, so unless $d$ is big enough to make this $n^2$ there will be some points farther from any shortcut endpoint than this. Therefore, the distance will remain at least proportional to $n/\sqrt k$, no matter where you put the shortcuts.

On the other hand, by spacing the shortcuts evenly throughout the grid, you can ensure that every point can reach at least one shortcut within distance proportional to $n/\sqrt k$. And by connecting the shortcuts themselves into a star topology (a tree with one interior node and $k$ leaves) you can make the distances between any two shortcuts negligible. So the best distance you can achieve is both upper-bounded and lower-bounded proportional to $n/\sqrt k$.

| cite | improve this answer | |
  • $\begingroup$ Thank you for response, but could you please explain where does 2k(2d+1)^2 and n/sqrt(k) comes from? Also d is distance from random node to nearest shortcut yes? Sorry for my probobly dummy questions but I'm just a begginer! $\endgroup$ – Kubinho10 Dec 29 '17 at 23:38
  • $\begingroup$ I simplified that part to $O(kd^2)$. It's just counting how many points are within that distance on a grid. $d$ can be any number you want it to be, and the $O(kd^2)$ bound on how many points are within that distance of shortcut endpoints will remain valid. $\endgroup$ – David Eppstein Dec 30 '17 at 4:45
  • $\begingroup$ Okey it's true that the best possible will always be n/sqrt(k),but still I don't know which nodes shuld i connect, because it does matter which nodes are connected. $\endgroup$ – Kubinho10 Dec 30 '17 at 11:14
  • $\begingroup$ And I would be gratefull if you could explain what big O is doing here:] $\endgroup$ – Kubinho10 Dec 30 '17 at 11:38
  • $\begingroup$ Re which nodes to connect: "by spacing the shortcuts evenly throughout the grid" $\endgroup$ – David Eppstein Dec 30 '17 at 16:11

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.