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.SWAT.2018.26
URN: urn:nbn:de:0030-drops-88521
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8852/
Go to the corresponding LIPIcs Volume Portal

Huang, Shang-En ; Pettie, Seth

Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts

pdf-format:
LIPIcs-SWAT-2018-26.pdf (0.5 MB)

Abstract

We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce the diameter of directed graphs. We show that any O(n)-size shortcut set cannot bring the diameter below Omega(n^{1/6}), and that any O(m)-size shortcut set cannot bring it below Omega(n^{1/11}). These improve Hesse's [Hesse, 2003] lower bound of Omega(n^{1/17}). By combining these constructions with Abboud and Bodwin's [Abboud and Bodwin, 2017] edge-splitting technique, we get additive stretch lower bounds of +Omega(n^{1/13}) for O(n)-size spanners and +Omega(n^{1/18}) for O(n)-size emulators. These improve Abboud and Bodwin's +Omega(n^{1/22}) lower bounds.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2018:8852,
  author =	{Shang-En Huang and Seth Pettie},
  title =	{{Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{26:1--26:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8852},
  URN =		{urn:nbn:de:0030-drops-88521},
  doi =		{10.4230/LIPIcs.SWAT.2018.26},
  annote =	{Keywords: additive spanners, emulators, shortcutting directed graphs}
}

Keywords: additive spanners, emulators, shortcutting directed graphs
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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