论文标题
在单调图中绘制距离
Sketching Distances in Monotone Graph Classes
论文作者
论文摘要
我们研究了两个播放器的通信问题，即确定两个顶点$ x，y $是否在图$ g $中附近，目的是确定允许使用恒定成本随机协议解决该问题的图形结构。等效地，我们考虑将恒定大小的随机标签（草图）分配给图形的顶点的问题，该标签允许邻接，确切的距离阈值或近似距离阈值以较高的可能性计算出标签的可能性。 我们的主要结果是，对于单调类别的类别类别：且仅当类具有支撑性的时，存在恒定大小的邻接草图；当且仅当类有界限时，存在精确距离阈值的恒定大小的草图；恒定大小的近似距离阈值（ADT）草图表明该类具有限制的扩展；任何类别的恒定扩展（即任何适当的次要封闭类）都有恒定尺寸的ADT草图；而且，一类可能在不承认恒定尺寸的ADT草图的情况下任意较小的扩展。
We study the two-player communication problem of determining whether two vertices $x, y$ are nearby in a graph $G$, with the goal of determining the graph structures that allow the problem to be solved with a constant-cost randomized protocol. Equivalently, we consider the problem of assigning constant-size random labels (sketches) to the vertices of a graph, which allow adjacency, exact distance thresholds, or approximate distance thresholds to be computed with high probability from the labels. 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 sketches for exact distance thresholds exist if and only if the class has bounded expansion; constant-size approximate distance threshold (ADT) sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has constant-size ADT sketches; and a class may have arbitrarily small expansion without admitting constant-size ADT sketches.
