2026-08-18T00:01:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17140 2024-03-06T10:59:04Z ddc:004 open_access

Sketching Distances in Monotone Graph Classes Esperet, Louis Harms, Nathaniel Kupavskii, Andrey adjacency labelling informative labelling distance sketching adjacency sketching communication complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louis Esperet and Nathaniel Harms and Andrey Kupavskii 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.18 urn:nbn:de:0030-drops-171406 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.18 eng https://creativecommons.org/licenses/by/4.0/legalcode