Optimal Labeling Schemes for $Γ$-Free Matrices

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Data Structures & Algorithms

• arXiv preprint · 21 October 2026

  Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling

  Sizhe Li, Nicolas Christianson and Tongxin Li
• arXiv preprint · 22 October 2026

  Optimal Mixing for Local Edge-Coloring Dynamics on Trees

  Haoran wang
• arXiv preprint · 22 October 2026

  Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references

  Haotian Tang
• arXiv preprint · 21 October 2026

  On the Largest Cardinality Subset Sum

  Deepak Bhati, Anubhav Dhar, Pranjal Dutta and 2 others
• arXiv preprint · 22 October 2026

  Near-Quadratic Time Multivariate Polynomial Interpolation

  Chandra Kanta Mohapatra

All new papers in Data Structures & Algorithms