On randomized representations of graphs using short labels

ABSTRACT

Informative labeling schemes consist in labeling the nodes of graphs so that queries regarding any two nodes (e.g., are the two nodes adjacent?) can be answered by inspecting merely the labels of the corresponding nodes. Typically, the main goal of such schemes is to minimize the label size, that is, the maximum number of bits stored in a label. This concept was introduced by Kannan et al. [STOC'88] and was illustrated by giving very simple and elegant labeling schemes, for supporting adjacency and ancestry queries in n-node trees; both these schemes have label size 2log n. Motivated by relations between such schemes and other important notions such as universal graphs, extensive research has been made by the community to further reduce the label sizes of such schemes as much as possible. The current state of the art adjacency labeling scheme for trees has label size log n+O(log*n) by Alstrup and Rauhe [FOCS'02], and the best known ancestry scheme for (rooted) trees has label size log n+O(√log n) by Abiteboul et al., [SICOMP 2006].

This paper aims at investigating the above notions from a probabilistic point of view. Informally, the goal is to investigate whether the label sizes can be improved if one allows for some probability of mistake when answering a query, and, if so, by how much. For that, we first present a model for probabilistic labeling schemes, and then construct various probabilistic one-sided error schemes for the adjacency and ancestry problems on trees. Some of our schemes significantly improve the bound on the label size of the corresponding deterministic schemes, while the others are matched with appropriate lower bounds showing that, for the resulting guarantees of success, one cannot expect to do much better in term of label size.

REFERENCES

• 1: Serge Abiteboul , Stephen Alstrup , Haim Kaplan , Tova Milo , Theis Rauhe, Compact Labeling Scheme for Ancestor Queries, SIAM Journal on Computing, v.35 n.6, p.1295-1309, 2006 [doi>10.1137/S0097539703437211]
• 2: Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
• 3: Stephen Alstrup , Philip Bille , Theis Rauhe, Labeling Schemes for Small Distances in Trees, SIAM Journal on Discrete Mathematics, v.19 n.2, p.448-462, 2005 [doi>10.1137/S0895480103433409]
• 4: Stephen Alstrup , Theis Rauhe, Small Induced-Universal Graphs and Compact Implicit Graph Representations, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.53-62, November 16-19, 2002
• 5: M. R. Capalbo, A small universal graph for bounded-degree planar graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.156-160, January 17-19, 1999, Baltimore, Maryland, United States
• 6: T.-H. Hubert Chan , Michael Dinitz , Anupam Gupta, Spanners with slack, Proceedings of the 14th conference on Annual European Symposium, p.196-207, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_20]
• 7: Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543648]
• 8: P. Fraigniaud and A. Korman. Compact Ancestry Labeling Schemes for Trees of Small Depth. Submitted, 2009. (see http://arxiv.org/pdf/0902.3081).
• 9: Sampath Kannan , Moni Naor , Steven Rudich, Implicit representation of graphs, SIAM Journal on Discrete Mathematics, v.5 n.4, p.596-603, Nov. 1992 [doi>10.1137/0405049]
• 10: Haim Kaplan , Tova Milo, Short and Simple Labels for Small Distances and Other Functions, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.246-257, August 08-10, 2001
• 11: Haim Kaplan , Tova Milo , Ronen Shabo, A comparison of labeling schemes for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.954-963, January 06-08, 2002, San Francisco, California
• 12: A. Korman, D. Peleg, and Y. Rodeh. Constructing Labeling Schemes Through Universal Matrices. Algorithmica, to appear.
• 13: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 14: David Peleg, Informative labeling schemes for graphs, Theoretical Computer Science, v.340 n.3, p.577-593, 31 August 2005 [doi>10.1016/j.tcs.2005.03.015]
• 15: R. Rado. Universal graphs and universal functions. Acta Arithmetica 9:331--340, 1964.
• 16: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures; Trees

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

General Terms:
Algorithms, Theory

Keywords:
adjacency labeling schemes, ancestry labeling schemes, distributed algorithms, probabilistic embeddings, universal graphs