Optimal Local Decompression on Graphs of Odd Maximum Degree

Abstract

An arbitrary subset of the edges of a communication graph can be stored as short vertex labels, provided a distributed decoder can recover each incident edge’s membership from a bounded neighborhood. Balliu, Brandt, Kuhn, Nowicki, Olivetti, Rotenberg and Suomela asked whether two bits per vertex suffice on cubic graphs. We answer this question affirmatively. More generally, for every fixed odd maximum-degree bound Δ ≥ 3, every edge subset of every graph of maximum degree at most Δ has a locally decodable encoding with exactly (Δ + 1)/2 bits per vertex. This uniform integer budget is optimal by counting, and decoding takes Δ^{O(Δ)} rounds in the LOCAL model. The construction uses the authors’ one-bit advice scheme for almost-balanced orientations. Separated marker vertices define bounded cells; nonmarker labels encode both a quotient-orientation advice bit and the membership bits of the edges owned by the cell. Reserving one of four labels as a marker leaves three data symbols, whose rate exceeds the cubic edge density. The orientation advice is decoded before ownership, avoiding a circular encoding. The encoder is unrestricted and the result is a locality theorem, with no claim of practical constants.