The Value of Steiner Hubs in Two-Hop Distance Labeling
Abstract
Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying arbitrary real values. On no family is the value of that freedom known. We determine it on ℓ1 products of betweenness-free metrics, those with no point between two others, a class containing every Hamming graph. The freedom is worth nothing when the factors have at most three letters, while from four letters on the largest saving is polynomial in the size of the product, attained on products of positively weighted stars. The d-dimensional hypercube is the two-letter case, and labeling it takes (5/2+o(1))d entries even with arbitrary hubs, matching the vertex-hub optimum of Goldberg, Razenshteyn, and Savchenko. Every lower bound here comes from one semidefinite program on a single factor, whose value Λ never exceeds the rate that vertex hubs already achieve on the Hamming graph; where Λ meets that ceiling, the freedom is worth nothing, and the ceiling is met exactly up to three letters.
Related
- Distance flexibility in spatial matching: the value of concentration
- The Higman-Sims graph and a geometric construction of the Steiner system $S(3,6,22)$
- Δ-Y Moves and Partial Steiner Systems
- Thresholds for ( n , q , 2)-Steiner systems via refined absorption
- Erdős-Ko-Rado properties of Steiner 2-designs
BibTeX
@misc{wang2026value,
title = {{The Value of Steiner Hubs in Two-Hop Distance Labeling}},
author = {Sichen Wang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01106},
eprint = {2611.01106},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01106},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Value of Steiner Hubs in Two-Hop Distance Labeling
AU - Sichen Wang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01106
UR - https://arxiv.org/abs/2611.01106
AB - Two-hop distance labelings were introduced in 2002 by Cohen, Halperin, Kaplan, and Zwick with hubs of two kinds: vertices of the graph, or, in their Steiner variant, arbitrary objects carrying arbitrary real values. On no family is the value of that freedom known. We determine it on ℓ_1 products of betweenness-free metrics, those with no point between two others, a class containing every Hamming graph. The freedom is worth nothing when the factors have at most three letters, while from four letters on the largest saving is polynomial in the size of the product, attained on products of positively weighted stars. The d-dimensional hypercube is the two-letter case, and labeling it takes (5/2+o(1))^d entries even with arbitrary hubs, matching the vertex-hub optimum of Goldberg, Razenshteyn, and Savchenko. Every lower bound here comes from one semidefinite program on a single factor, whose value Λ never exceeds the rate that vertex hubs already achieve on the Hamming graph; where Λ meets that ceiling, the freedom is worth nothing, and the ceiling is met exactly up to three letters.
ER -