Bundling all shortest paths

Michał Dębski , Konstanty Junosza-Szaniawski , Zbigniew Lonc

Abstract

We study the problem of finding a minimum bundling set in a graph, where a bundling set B is a set of vertices such that every shortest path can be extended to a shortest path from a vertex in B to some other vertex. If G is a weighted graph, we denote the size of a minimum bundling set in G by b(G). Bundling sets can be used by the ALT algorithm that finds shortest paths in weighted graphs. For a fixed bundling set B in a weighted graph G, after some preprocessing using O(|B||V(G)|) memory, it is possible to determine the distance between any two vertices in time O(|B|). Therefore, it is desirable to find small bundling sets.We show that determining b(G) is NP-hard and give a 2-approximation algorithm.Moreover we characterize simple graphs with b=1 and subgraphs of grids with b=2.We also introduce the parameter b∗(G) equal to the minimum of b(H) over all weighted graphs H such that G is an isometric subgraph of H, i.e. for every two vertices u,v of Gthe distances from u to v in G and in H are the same. Sometimes b∗(G) is much smaller than b(G) and a further improvement of performance of route planning can be obtained. As a part of a proof, we show that at least Θ(logn/loglogn) trianglefree graphs are needed to cover a complete graph on n vertices, which may be of independent interest.