Optimal labeling schemes enable fast queries on special binary matrices
Optimal Labeling Schemes for $Γ$-Free Matrices
Data Structures and Algorithms
Summary
This paper studies how to label the rows and columns of certain special binary matrices so that you can quickly find any entry just by looking at the labels. The matrices studied avoid a specific small pattern called gamma. The authors show how to assign short labels that let you find any entry in constant time, and that their labeling is as efficient as possible given the constraints. They also provide a way to build these labels and related structures efficiently. This has implications for representing some types of graphs compactly while supporting fast queries.
What this means in practice
- •For graph database developers: Create highly compact graph representations that allow adjacency queries in constant time for strongly chordal and chordal bipartite graphs.
- •For data structure engineers: Implement efficient data structures for certain binary matrices enabling fast lookup operations with provably optimal label sizes.
Authors
Sankardeep Chakraborty, Seungbum Jo
Abstract
We study labeling schemes for $p \times q$ $Γ$-free binary matrices, which do not contain a submatrix of the form $Γ= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. We give a labeling scheme that uses $O(\log^2 N)$-bit labels for rows and columns, where $N=p+q$, such that any matrix entry can be determined from the corresponding two labels in constant time in the word RAM model. The worst-case label size matches the counting lower bound up to constant factors. We also show that the entrywise least $Γ$-free supermatrix of an arbitrary $p\times q$ binary matrix, together with its labels, can be constructed in $O(pq)$ time. Our construction represents a $Γ$-free matrix by a sequence of rooted forests, where each column corresponds to a node and the $1$-entries of each row form a root path in its corresponding forest. For $n$-vertex strongly chordal and chordal bipartite graphs, our result gives asymptotically optimal $O(\log^2 n)$-bit adjacency labeling schemes with constant-time queries. These results answer both representation questions posed by Spinrad in 1995.