We study the question of "how robust are the known lower bounds of labeling schemes when one increases the number of consulted labels". Let f be a function on pairs of vertices. An f -labeling scheme for a family of graphs F labels the vertices of all graphs in F such that for every graph G ∈ F and every two vertices u, v ∈ G, the value f (u, v) can be inferred by merely inspecting the labels of u and v. This paper introduces a natural generalization: the notion of f -labeling schemes with queries, in which the value f (u, v) can be inferred by inspecting not only the labels of u and v but possibly the labels of some additional vertices. We show that inspecting the label of a single additional vertex (one query) enables us to reduce the label size of many labeling schemes significantly. In particular, we show that to support the distance function on n-node trees as well as the flow function on n-node general graphs, O(log n + log W )-bit labels are sufficient and necessary, where W is the maximum (integral) capacity of an edge. We note that it was shown that any labeling scheme (without queries) supporting either the flow function on general graphs or the distance function on trees, must have label size Ω(log 2 n + log n log W ). Using a single query, we also show a routing labeling scheme in the fixed-port model using O(log n)-bit labels, while the lower bound on the label size of any such routing labeling scheme (without queries) is Ω(log 2 n/log log n). We note that all our labeling schemes with queries have asymptotically optimal label size. We then show several extensions. In particular, we show that our labeling schemes with queries on trees can be extended to the dynamic scenario by some adaptations of known model translation methods. Second, we show that the study of the queries model can help with the traditional model too. That is, using ideas from our routing labeling scheme with one query, we show how to construct a 3-approximation routing scheme without queries in the fixed-port model with Θ(log n)-bit labels. Finally, we turn to a non-distributed environment and first translate known results on finding NCA to supporting distance queries. We then use the above to show that one can preprocess a general weighted graph using almost linear space so that flow queries can be answered in almost constant time.
In REF a model (1-query) is studied where one, in addition to the label of the input nodes, can access the label of one additional node.
Labeling Schemes with Queries
ArXiv
ArXiv
Computer Science