Metraipolis › archive › dc_a02ebf12a2f3

Hardness Results for Approximate Distance Labeling in Sparse Graphs — arXiv:2611.02821

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02821
License (as archived)
CC0-1.0
Archived
2026-11-03T11:45:44.855Z
SHA-256 of the archived text
0fe8461d5fad68672d1960a055b1f27e654f06d2ec7a6e838c6f6901a801fcd8
Stable URL of this page
https://metraipolis.com/documento/dc_a02ebf12a2f3

How to cite

Hardness Results for Approximate Distance Labeling in Sparse Graphs — arXiv:2611.02821 — arXiv (en), https://arxiv.org/abs/2611.02821 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a02ebf12a2f3 (Metraipolis archive dc_a02ebf12a2f3, sha256 0fe8461d5fad68672d1960a055b1f27e654f06d2ec7a6e838c6f6901a801fcd8)
BibTeX
@misc{dca02ebf12a2f3,
  title = {Hardness Results for Approximate Distance Labeling in Sparse Graphs — arXiv:2611.02821},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02821},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a02ebf12a2f3; sha256 0fe8461d5fad68672d1960a055b1f27e654f06d2ec7a6e838c6f6901a801fcd8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02821. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uznański, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index communication problem, exact distance labeling for sparse unweighted graphs requires near-linear label size. Their construction also gives lower bounds for stretch $1+o(1)$, but does not rule out substantially smaller labels for stretch $1+\varepsilon$, where $\varepsilon>0$ is fixed. We prove lower bounds for this $(1+\varepsilon)$-stretch regime through a density/stretch tradeoff. For every constant integer $k\ge 1$, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with $m=O(n^{1+1/k})$ edges requires maximum label size at least $\mathrm{SumIndex}(n)/2^{O_k(\sqrt{\log n})}$ for infinitely many values of $n$. Thus, under the conjecture that $\mathrm{SumIndex}(n)=n^{1-o(1)}$, the maximum label size must be $n^{1-o(1)}$. The main new ingredient is an unweighted graph construction based on $3$-AP-free sets, which replaces the weighted uniqueness mechanism of the previous Sum-Index reduction by an additive uniqueness mechanism and keeps the relevant critical paths short enough to obtain a constant multiplicative distance gap. The same construction also yields near-tight lower bounds for related $2$-hop structures, including hub labeling schemes, shortcut sets, and approximate distance hopsets.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.02821 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.251Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).