Labeling Schemes with Queries
Amos Korman, Shay Kutten
Abstract: We study the question of ``how robust are the known lower bounds of labeling
schemes when one increases the number of consulted labels''. Let be a function on pairs
of vertices. An -labeling scheme for a family of graphs labels the vertices of all
graphs in such that for every graph and every two vertices in, the
value can be inferred by merely inspecting the labels of and.
This paper introduces a natural generalization: the notion of -labeling schemes with
queries, in which the value can be inferred by inspecting not only the labels of
and but possibly the labels of some additional vertices. We show that inspecting
the label of a single additional vertex (one {\em query}) enables us to reduce the label
size of many labeling schemes significantly.