License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.6
URN: urn:nbn:de:0030-drops-112217
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11221/
Go to the corresponding LIPIcs Volume Portal

Filtser, Arnold

On Strong Diameter Padded Decompositions

pdf-format:
LIPIcs-APPROX-RANDOM-2019-6.pdf (0.8 MB)

Abstract

Given a weighted graph G=(V,E,w), a partition of V is Delta-bounded if the diameter of each cluster is bounded by Delta. A distribution over Delta-bounded partitions is a beta-padded decomposition if every ball of radius gamma Delta is contained in a single cluster with probability at least e^{-beta * gamma}. The weak diameter of a cluster C is measured w.r.t. distances in G, while the strong diameter is measured w.r.t. distances in the induced graph G[C]. The decomposition is weak/strong according to the diameter guarantee.
Formerly, it was proven that K_r free graphs admit weak decompositions with padding parameter O(r), while for strong decompositions only O(r^2) padding parameter was known. Furthermore, for the case of a graph G, for which the induced shortest path metric d_G has doubling dimension ddim, a weak O(ddim)-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known.
We construct strong O(r)-padded decompositions for K_r free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension ddim we construct a strong O(ddim)-padded decomposition, which is also tight. We use this decomposition to construct (O(ddim),O~(ddim))-sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.

BibTeX - Entry

@InProceedings{filtser:LIPIcs:2019:11221,
  author =	{Arnold Filtser},
  title =	{{On Strong Diameter Padded Decompositions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11221},
  URN =		{urn:nbn:de:0030-drops-112217},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.6},
  annote =	{Keywords: Padded decomposition, Strong Diameter, Sparse Cover, Doubling Dimension, Minor free graphs, Unique Games, Spanners, Distance Oracles}
}

Keywords: Padded decomposition, Strong Diameter, Sparse Cover, Doubling Dimension, Minor free graphs, Unique Games, Spanners, Distance Oracles
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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