Document Open Access Logo

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

Authors Shang-En Huang, Seth Pettie

PDF

File

Thumbnail PDF
PDF
LIPIcs.SWAT.2018.26.pdf
  • Filesize: 464 kB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • additive spanners
  • emulators
  • shortcutting directed graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Shang-En Huang and Seth Pettie. Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.26

Author Details

Shang-En Huang
  • University of Michigan, USA
Seth Pettie
  • University of Michigan, USA

References

  1. Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. J. ACM, pages 28:1-28:20, 2017. Google Scholar
  2. Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear additive spanners. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017. Google Scholar
  3. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. Google Scholar
  4. Noga Alon. Testing subgraphs in large graphs. Random Structures &Algorithms, 21(3-4):359-370, 2002. Google Scholar
  5. Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners and (α, β)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010. Google Scholar
  6. Felix Behrend. On sets of integers which contain no three terms in arithmetic progression. Proc. Nat. Acad. Sci., 32:331-332, 1946. Google Scholar
  7. Greg Bodwin. Linear size distance preservers. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 600-615, 2017. Google Scholar
  8. Greg Bodwin and Virginia Vassilevska Williams. Better distance preservers and additive spanners. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. Google Scholar
  9. Gregory Bodwin and Virginia Vassilevska Williams. Very sparse additive spanners and emulators. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pages 377-382, 2015. Google Scholar
  10. Imre Bárány and David G. Larman. The convex hull of the integer points in a large ball. Mathematische Annalen, 312(1):167-181, 1998. Google Scholar
  11. Shiri Chechik. New additive spanners. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 498-512, 2013. Google Scholar
  12. Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics, pages 463-501, 2006. Google Scholar
  13. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Google Scholar
  14. Michael Elkin and David Peleg. (1+ε,β)-spanner constructions for general graphs. SIAM Journal on Computing, 33(3):608-631, 2004. Google Scholar
  15. Jeremy T. Fineman. Nearly work-efficient parallel algorithm for digraph reachability. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 2018. Google Scholar
  16. William Hesse. Directed graphs requiring large numbers of shortcuts. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003. Google Scholar
  17. Shang-En Huang and Seth Pettie. Thorup-Zwick emulators are universally optimal hopsets. CoRR, abs/1705.00327, 2017. URL: http://arxiv.org/abs/1705.00327.
  18. Mathias Bæk Tejs Knudsen. Additive spanners: A simple construction. In Scandinavian Workshop on Algorithm Theory (SWAT), pages 277-281, 2014. Google Scholar
  19. Seth Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1):7, 2009. Google Scholar
  20. Mikkel Thorup. On shortcutting digraphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 205-211. Springer, 1992. Google Scholar
  21. Mikkel Thorup. Shortcutting planar digraphs. Combinatorics, Probability and Computing, 4(3):287-315, 1995. Google Scholar
  22. Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. Google Scholar
  23. David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact