License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.18
URN: urn:nbn:de:0030-drops-171406
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17140/
Go to the corresponding LIPIcs Volume Portal

Esperet, Louis ; Harms, Nathaniel ; Kupavskii, Andrey

Sketching Distances in Monotone Graph Classes

pdf-format:
LIPIcs-APPROX18.pdf (0.9 MB)

Abstract

We study the problems of adjacency sketching, small-distance sketching, and approximate distance threshold (ADT) sketching for monotone classes of graphs. The algorithmic problem is to assign random sketches to the vertices of any graph G in the class, so that adjacency, exact distance thresholds, or approximate distance thresholds of two vertices u,v can be decided (with probability at least 2/3) from the sketches of u and v, by a decoder that does not know the graph. The goal is to determine when sketches of constant size exist.
Our main results are that, for monotone classes of graphs: constant-size adjacency sketches exist if and only if the class has bounded arboricity; constant-size small-distance sketches exist if and only if the class has bounded expansion; constant-size ADT sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has a constant-size ADT sketch; and a class may have arbitrarily small expansion without admitting a constant-size ADT sketch.

BibTeX - Entry

@InProceedings{esperet_et_al:LIPIcs.APPROX/RANDOM.2022.18,
  author =	{Esperet, Louis and Harms, Nathaniel and Kupavskii, Andrey},
  title =	{{Sketching Distances in Monotone Graph Classes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{18:1--18:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17140},
  URN =		{urn:nbn:de:0030-drops-171406},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.18},
  annote =	{Keywords: adjacency labelling, informative labelling, distance sketching, adjacency sketching, communication complexity}
}

Keywords: adjacency labelling, informative labelling, distance sketching, adjacency sketching, communication complexity
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI