PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Labeling Schemes for $\Gamma$-Free Matrices

Sankardeep Chakraborty, Seungbum Jo

arXiv:2610.29184v1cs.DS

TL;DR

For strongly chordal and chordal bipartite graphs, matching labeling bounds do not follow from counting alone. The paper represents Γ-free matrices with a sequence of forests and gives asymptotically optimal labels supporting constant-time queries.

  • Problem

    For strongly chordal and chordal bipartite graphs, matching adjacency-labeling bounds do not follow from counting alone.

    Source: §1 · p. 2

  • Method

    Represent Γ-free matrices with an ancestor-monotone sequence of ordered forests, where each nonempty row support is a complete root path.

    Source: §2.1 · p. 3

  • Results

    O(log^2 N)-bit row and column labels determine any Γ-free matrix entry in O(1) time, with asymptotically optimal worst-case label size.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    The scheme gives asymptotically optimal O(log^2 n)-bit adjacency labels with constant-time queries for strongly chordal and chordal bipartite graphs, answering both representation questions posed by Spinrad.

    Source: §1 · p. 2

    The constant-time guarantee assumes a word RAM with w = c⌈log N⌉-bit words and standard operations, including multiplication.

    Source: §3 · p. 6

Abstract

from arXiv · show

We study labeling schemes for $p \times q$ $\Gamma$-free binary matrices, which do not contain a submatrix of the form $\Gamma = \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 $\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.

1 Introduction

The paper gives an asymptotically optimal, constant-time labeling scheme for Γ-free matrices, answering Spinrad’s open adjacency-labeling questions for strongly chordal and chordal bipartite graphs. It builds the labels from an evolving sequence of rooted forests, using rank-stable solid-path identifiers to encode forest history compactly.

1 Introduction

  • O(log^2 N)-bit row and column labels determine any Γ-free matrix entry in O(1) word-RAM time, and the worst-case label size is asymptotically optimal.Here N = p + q.Source: §1 · p. 2
  • For n-vertex strongly chordal and chordal bipartite graphs, the labeling scheme gives asymptotically optimal O(log₂ n)-bit adjacency labels and constant-time adjacency queries, answering both representation questions posed by Spinrad.These classes have superfactorial but subquadratic speed 2^Θ(n log₂ n), so matching labeling bounds do not follow from counting alone.Source: §1 · p. 2

2.1 Forest representation of Γ-free matrices

  • A Γ-free matrix is characterized by an ancestor-monotone sequence of forests in which each nonempty row support is a complete root path; the construction arranges each row’s nodes and their ancestors into an ordered path.The final forest alone may not preserve earlier row supports as root paths.Source: §2.1 · pp. 3–4

2.2 Rank-based path decomposition

  • Rank-based decomposition makes forest history compact: stable nodes retain their solid-path identifiers, and each node changes rank and identifier only O(log(q + 1)) times.Ranks are based on descendant-set sizes; solid edges join equal-rank nodes, forming vertex-disjoint paths.Source: §2.2 · pp. 4–5

2.3 Construction of the labeling scheme

  • Column labels store timestamped rank and path-identifier records, while row labels store intersected path identifiers and boundaries; together they support constant-time entry queries.Each label uses O(log^2 N) bits, and predecessor search is constant-time in the word RAM model with multiplication.Source: §2.3 · p. 5

3 Model and Notation

The section defines Γ-freeness, matrix labels, and the decoder model. The decoder determines an entry using only its row and column labels, with word-RAM operations available in constant time.

3 Model and Notation

  • Γ-freeness forbids an ordered pair of rows and columns with three 1-entries and a 0 in the lower-right position.Equivalently, if h < i and a < b have M(h,a) = M(h,b) = M(i,a) = 1, then M(i,b) = 1.Source: §3 · p. 6
  • A matrix-labeling scheme assigns labels to each row and column, and a fixed decoder uses only the corresponding pair to determine an entry.The decoder is independent of the matrix and receives no matrix-dependent information beyond the two labels.Source: §3 · p. 6
  • The word RAM uses w = c⌈log N⌉-bit words and supports standard operations, including multiplication, in constant time.Labels are stored as arrays of words, and any word in either supplied label can be accessed in constant time.Source: §3 · p. 6
  • A monotone forest representation is a sequence of ordered forests preserving ancestor relations, with each nonempty row represented as a root path.For row i, its support is Anc_Fi(si); the initial forest F0 is edgeless.Source: §3 · p. 6

4 Forest Characterization of Γ-Free Matrices

The section characterizes Γ-free matrices through an evolving sequence of ordered forests. Processing each row arranges its support into a root path while preserving earlier ancestor relations, and the converse also holds.

4 Forest Characterization of Γ-Free Matrices

  • For each row, the construction gathers its support and the ancestors of those columns in the preceding forest, then arranges that set into an increasing path.Nodes outside the set retain their parent pointers, and an empty row leaves the forest unchanged.Source: §4 · p. 6
  • Each update produces an ordered forest and preserves all ancestor relations from the preceding forest.The update set is upward closed, so a previous parent-child relation remains an ancestor relation after rearrangement.Source: §4 · pp. 6–7
  • For a Γ-free matrix, the update set equals the row support, so every nonempty row support becomes a complete root path.The construction’s key inclusion follows from Γ-freeness and the witnessed parent edges.Source: §4 · p. 7
  • A matrix is Γ-free if and only if it has an ancestor-monotone sequence of ordered forests representing each nonempty row as a root path.In the converse, a prior row’s ordered path and preserved ancestor relations force the Γ-free implication for any later row.Source: §4 · p. 7

5 Rank Stability and Persistent Identifiers

The section decomposes forests into rank-based solid paths and shows that stable nodes retain their path identities across updates. These properties bound the history needed to represent each node.

5 Rank Stability and Persistent Identifiers

  • Each node’s subtree size and rank are nondecreasing across the forest sequence, so its rank changes at most L times.Here rank is floor(log subtree size), and L = floor(log q).Source: §5 · pp. 7–8
  • Solid edges partition each forest into vertex-disjoint paths, and a root path intersects at most L + 1 such paths.A node has at most one solid child, and each root path intersects at most one solid path of each rank.Source: §5 · p. 8
  • Two nodes share a solid path exactly when they are comparable and have the same rank.Along a root path, equal-rank endpoints force all intervening edges to be solid.Source: §5 · p. 8
  • Stable nodes retain their solid-path identifiers across transitions, using O(q log(q + 1)) distinct identifiers in total.A fresh identifier is needed only for a new path with no stable node; it is charged to a node whose rank increased.Source: §5 · p. 9
  • Each node’s change list contains at most 1 + rank_p(x) records, and all change lists together contain O(q log(q + 1)) records.A node’s state changes only when its rank increases, with an initial record included.Source: §5 · p. 9

6 Row and Column Labels

The section encodes the evolving forest states in row and column labels, then decodes entries by matching rank-path information. Binary search gives a faster-than-linear query, and predecessor search yields constant-time decoding while retaining the stated label-size bound.

6 Row and Column Labels

  • Monotone-forest matrices admit O(log2(q + 1) + log N)-bit row and column labels with O(1)-time entry queries on the word RAM.The membership test matches a column’s active solid-path identifier with the row’s identifier and checks a boundary.Source: §6 · p. 10
  • Row labels store a version and rank-indexed path identifiers and boundaries; column change-list timestamps are replaced by versions to keep their representation compact.Each row support intersects at most one solid path of each rank, and each column’s state persists between successive records.Source: §6 · p. 10

6.1 Label Construction and Binary-Search Decoding

  • Each row or column label’s fields require O(log2(q + 1)) bits total; packing them consecutively into w-bit words adds at most O(w) = O(log N) padding, yielding O(log2(q + 1) + log N) bits per label.Source: §6.1 · p. 11
  • The binary-search decoder uses O(1 + log log(q + 1)) time to find a column’s state at the queried version.It searches the column’s version array for the most recent record not exceeding the row’s version; the membership test then determines the entry.Source: §6.1 · p. 11

6.2 Constant-Time Decoding

  • Static predecessor structures on column version numbers replace binary search and retrieve the active state in constant time.The structures fit within the column labels without increasing their asymptotic size; the remaining decoding steps take constant time.Source: §6.2 · pp. 11–12

7 Information-Theoretic Optimality

The worst-case label size for Γ-free matrices is Θ(log² N), matching the counting lower bound. Storing all labels also gives an asymptotically optimal centralized representation with constant-time entry queries.

7 Information-Theoretic Optimality

  • Θ(log² N) is the worst-case maximum label length for Γ-free matrices, matching the upper and counting lower bounds.The counting argument gives the lower bound even for fixed dimensions, with s = min{p, q}.Source: §7 · pp. 12–13
  • For N = p + q, every p × q Γ-free matrix has an O(N log2 N)-bit centralized representation with O(1)-time entry queries on the word RAM, and this space is worst-case asymptotically optimal.Source: §7 · p. 13

8 Computing the Γ-Free Closure

The forest construction extends to arbitrary binary matrices and produces their entrywise least Γ-free supermatrix. This canonical closure is computable in O(pq) time and equals the input exactly when that input is already Γ-free.

8 Computing the Γ-Free Closure

  • The construction builds forests row by row, extending each row’s support to a root path while preserving containment in every Γ-free supermatrix.Parent edges have witness rows whose two endpoints are both 1, forcing subsequent entries along the path in any Γ-free supermatrix.Source: §8 · pp. 13–14
  • For any binary matrix, the forest construction produces its entrywise least Γ-free supermatrix, the canonical Γ-free closure, in O(pq) time.The output contains the input and is contained in every Γ-free supermatrix of that input.Source: §8 · p. 14
  • The closure equals the input if and only if the input is Γ-free, and it also admits constant-time entry decoding with O(log²(q + 1) + log N)-bit labels.The labels follow from the forest representation and Theorem 6.1.Source: §8 · p. 14

9 Construction Time

The forest construction, closure, and labels can be built in O(pq) time. Γ-free orderings transfer the labeling scheme to totally balanced matrices, chordal bipartite and strongly chordal graphs, strongly chordal digraphs, and β-acyclic hypergraphs.

9 Construction Time

  • O(pq) time suffices to construct an arbitrary matrix’s Γ-free closure and O(log²(s + 1) + log N)-bit labels for O(1)-time entry queries.The construction orients the matrix to have r = max{p, q} rows and s = min{p, q} columns; forest updates and label maintenance take O(rs) time.Source: §9 · pp. 14–15

10 Applications

  • The scheme applies to graph and hypergraph classes whose associated matrices admit Γ-free orderings, which are needed for construction but not for queries.Concatenating labels gives the corresponding centralized representations.Source: §10 · p. 15

10.1 Totally Balanced Matrices

  • Totally balanced matrices admit O(log² N)-bit labels with O(1)-time entry queries, constructible in O(pq) time.Independent row and column permutations make such matrices Γ-free.Source: §10.1 · p. 15

10.2 Chordal Bipartite Graphs

  • Chordal bipartite graphs admit asymptotically optimal O(log² n)-bit adjacency labels, O(1)-time queries, and O(n²)-time construction.Their biadjacency matrices can be independently permuted into Γ-free order.Source: §10.2 · p. 15

10.3 Strongly Chordal Graphs and Digraphs

  • Strongly chordal graphs, strongly chordal split graphs, and strongly chordal digraphs each admit asymptotically optimal O(log² n)-bit labels with O(1)-time queries and O(n²)-time construction.For graphs, the scheme uses a shared vertex ordering for rows and columns of the closed-neighborhood matrix; for digraphs, it uses a Γ-free vertex ordering.Source: §10.3 · pp. 16–17

10.4 β-Acyclic Hypergraphs

  • β-acyclic hypergraphs admit asymptotically optimal O(log² N)-bit incidence labels, O(1)-time queries, and O(|V||E|)-time construction.The label-size bound remains optimal for simple hypergraphs with nonempty hyperedges.Source: §10.4 · p. 17

11 Related Work

Prior work established counting bounds and compact representations for Γ-free matrices, but efficient entry access and matching short labels did not follow automatically. The paper’s structural approach connects Γ-free matrices to several matrix and graph classes while addressing those representation gaps.

11 Related Work

  • Spinrad gave an asymptotically optimal global representation of Γ-free matrices, but it did not provide efficient access to individual entries.Dahlhaus studied compact graph representations and proposed an auxiliary structure for polylogarithmic-time adjacency queries.Source: §11 · pp. 17–18
  • Counting bounds alone do not always yield matching labeling schemes: hereditary classes with 2^O(n log n) labeled n-vertex graphs can require n^Ω(1)-bit labels [HH22].For strongly chordal and chordal bipartite graphs, μ_C(n) = Θ(log₂ n), but the μ_C(n)+o(n) bound does not establish O(log₂ n)-bit labels.Source: §11 · p. 18
  • Structural labeling methods include graph product structure for planar and minor-closed classes, while strongly chordal and chordal bipartite graphs contain all cliques or complete bipartite graphs, respectively.Consequently, neither class has bounded treewidth or belongs to a fixed proper minor-closed class.Source: §11 · p. 18
  • The paper’s forest-history encoding draws on classical solid-path decompositions and persistence for accessing earlier shared-data-structure versions.Prior ancestry-labeling work includes constant-time static tree labels of log n + O(log log n) bits [FK16].Source: §11 · pp. 18–19

12 Conclusion and Further Directions

The conclusion restates the optimal labeling result and identifies open directions for succinct graph representations, richer navigation, and matrices requiring multiple historical root paths. It also proposes studying evolving structures whose local identities change only a few times.

12 Conclusion and Further Directions

  • The paper concludes that Γ-free matrices admit asymptotically optimal row and column labels supporting constant-time entry queries.The conclusion identifies monotone forests and persistent path identities as the main ingredient.Source: §12 · p. 19
  • For strongly chordal and chordal bipartite graphs, open questions include succinct constant-time adjacency and O(n log2 n)-bit representations for richer navigation queries.The listed targets include neighbor reporting, distance queries, and shortest-path reporting.Source: §12 · p. 19
  • The proposed parameter k is the minimum number of complete root paths whose union represents each row in an ancestor-monotone forest history; k ≤ 1 characterizes Γ-free matrices for fixed orders.The authors propose characterizing small-k matrices and graphs, studying the complexity of computing k, and investigating labeling bounds in terms of k.Source: §12 · p. 19
  • The paper suggests seeking other evolving structures in which local identities change only a small number of times, as a route to compact labels for historical queries.Source: §12 · p. 19

AI Methodology

  • The authors report using AI tools for presentation, illustrative figures and examples, proof checking, and manuscript feedback, while stating that they developed and independently verified the research.Source: AI Methodology · p. 19

A Supplementary Construction Details

The supplementary encoder constructs labels by processing rows and maintaining canonical forest states and histories. A proposition relates each forest's ancestor relation to reachability in Spinrad's column digraph.

A.1 Encoder Algorithm

  • The encoder processes a Γ-free matrix row by row, updating the canonical forest and recording row snapshots and column histories for label serialization.It initializes singleton paths, updates each row's path, computes ranks and solid paths, and assigns path identifiers.Source: §A.1 · p. 23
  • Stable nodes retain their solid-path identifier across updates; paths without an inherited identifier receive fresh ones.Source: §A.1 · p. 23
  • The encoder stores a row snapshot and appends column-history records, then serializes both using the labeling format and a predecessor structure for constant-time decoding.Source: §A.1 · p. 23
  • The algorithm's row supports are root paths, and its state records and snapshots satisfy the labeling theorem's conditions.Its construction time is analyzed in Theorem 9.1.Source: §A.1 · p. 23

A.2 Relationship to Spinrad’s Construction

  • For every prefix, the forest's reflexive ancestor relation equals reachability in Spinrad's digraph on columns, whose arcs encode co-occurrence in a row prefix.Consequently, the forest is the transitive reduction of that reachability relation.Source: §A.2 · pp. 23–24
  • The correspondence follows because forest parent edges have row witnesses, while each co-occurrence arc induces an ancestor relation preserved by later forest updates.Source: §A.2 · p. 24

B An Example of the Labeling Scheme

The example traces a nine-row, eight-column Γ-free matrix through its forest history, path ranks and identifiers, row snapshots, and stored column records. It illustrates how the representation preserves enough history to recover row supports and entry labels.

B An Example of the Labeling Scheme

B.1 The matrix and its forest history

  • In the example matrix, rows 1–3 create components, rows 4 and 6 merge them, and rows 5, 7, and 9 leave the forest unchanged while row 8 is empty.The resulting matrix is Γ-free.Source: §B.1 · p. 25

B.2 Ranks and path identifiers

  • Path identifiers change only when a node's rank increases, so nodes retaining rank keep their identifiers even when their solid paths change.Column 8's four history records attain the L + 1 bound.Source: §B.2 · p. 26

B.3 Row snapshots

  • Each row snapshot records identifiers and boundaries by rank, allowing it to specify the relevant portions of the row's root path.For row 5, the boundary excludes column 2 despite its matching identifier, while rank 2 covers the path beginning at column 4.Source: §B.3 · pp. 27–28

B.4 Updates and stored records

  • The updates append records only when a column's rank or path identifier changes, while row snapshots use the forest version associated with each update.At the first merge, column 3 keeps its rank and identifier despite a changed solid path, so it needs no new record.Source: §B.4 · p. 28
  • The example's column histories contain eight initial records and twelve appends across the nine rows.Source: §B.4 · p. 28

B.5 Entry queries

The entry-query examples show how versioned column records, path identifiers, and row boundaries determine matrix entries. Deleting one entry creates a forbidden pattern, and the canonical forest update restores the least Γ-free completion.

B.5 Entry queries

  • The decoder selects the latest column record at or before the row's version, then checks the row's identifier and boundary for that rank to determine the entry.The boundary selects the relevant suffix of a solid path.Source: §B.5 · p. 29, Figure 6 · p. 29
  • The example evaluates all 72 entries and reports agreement with the original matrix.Source: §B.5 · p. 30

B.6 Closure after deleting an entry

  • Deleting entry (5, 8) creates a forbidden pattern, and the forest update restores that entry to recover the Γ-free matrix.Every Γ-free supermatrix of the modified matrix must contain (5, 8), so the recovered matrix is its Γ-free closure.Source: §B.6 · p. 30, Figure 7 · p. 30
Loading 2610.29184v1…