Optimal Labeling Schemes for $\Gamma$-Free Matrices

Abstract

We study labeling schemes for $p\times q$ $\Gamma$-free binary matrices, which do not contain a submatrix of the form $\Gamma =\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$. 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 $\Gamma$-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 $\Gamma$-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.