For fixed @math , we consider the task of adding to a graph @math a set of weighted shortcut edges on the same vertex set, such that the length of a shortest @math -hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in @math . A set of shortcut edges with this property is called an exact @math -hopset and may be applied in processing distance queries on graph @math . In particular, a @math -hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on @math -hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that @math -hopsets require exponentially fewer shortcuts per node than any previously described distance oracle while incurring only a quadratic increase in the query decoding time, and actually offer a speedup when compared to simple oracles based on a direct application of @math -hopsets. Finally, we consider the problem of computing minimum-size @math -hopset (for any @math ) for a given graph @math , showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When @math , for a given bound on the space used by the distance oracle, we provide a construction of hopsets achieving polylog approximation both for space and query time compared to the optimal @math -hopset oracle given the space bound.
Hub sets with near to optimal size can be constructed in polynomial time. A greedy setcover-type @math -approximation algorithm (with respect to average size of a hub set) was proposed by @cite_21 . For the case of USP graphs, this approximation ratio was improved by @cite_40 to the logarithm of the graph hop-diameter, i.e., the maximum number of hops of a shortest path in @math .
@cite_40 @cite_21
2550610852 1994924587
There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the hub labeling framework. In this paper, we study the approximability of the Hub Labeling problem. We prove a hardness of Ω(log n) for Hub Labeling, matching known approximation guarantees. The hardness result applies to graphs that have multiple shortest paths between some pairs of vertices. No hardness of approximation results were known previously. Then, we focus on graphs that have a unique shortest path between each pair of vertices. This is a very natural family of graphs, and much research on the Hub Labeling problem has studied such graphs. We give an O(log D) approximation algorithm for graphs of shortest-path diameter D with unique shortest paths. In particular, we get an O(log log n) approximation for graphs of polylogarithmic diameter, while previously known algorithms gave an O(log n) approximation. Finally, we present a polynomial-time approximation scheme (PTAS) and quasi-polynomial-time algorithms for Hub Labeling on trees; additionally, we analyze a simple combinatorial heuristic for Hub Labeling on trees, proposed by Peleg in 2000. We show that this heuristic gives an approximation factor of 2. Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. We propose a new data structure for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v. Our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. For shortest paths, such a cover is a collection S of shortest paths such that, for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from S. We describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. Our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries. We study the proposed data structure using a combination of theoretical and experimental means. We implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. Our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.