Document Open Access Logo

Roundtrip Spanners with (2k-1) Stretch

Authors Ruoxu Cen, Ran Duan, Yong Gu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.24.pdf
  • Filesize: 487 kB
  • 11 pages

Document Identifiers

Author Details

Ruoxu Cen
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Ran Duan
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Yong Gu
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China

Cite As Get BibTex

Ruoxu Cen, Ran Duan, and Yong Gu. Roundtrip Spanners with (2k-1) Stretch. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 24:1-24:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.24

Abstract

A roundtrip spanner of a directed graph G is a subgraph of G preserving roundtrip distances approximately for all pairs of vertices. Despite extensive research, there is still a small stretch gap between roundtrip spanners in directed graphs and undirected graphs. For a directed graph with real edge weights in [1,W], we first propose a new deterministic algorithm that constructs a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log (nW)) edges for every integer k > 1, then remove the dependence of size on W to give a roundtrip spanner with (2k-1) stretch and O(k n^(1+1/k) log n) edges. While keeping the edge size small, our result improves the previous 2k+ε stretch roundtrip spanners in directed graphs [Roditty, Thorup, Zwick'02; Zhu, Lam'18], and almost matches the undirected (2k-1)-spanner with O(n^(1+1/k)) edges [Althöfer et al. '93] when k is a constant, which is optimal under Erdös conjecture.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Graph theory
  • Deterministic algorithm
  • Roundtrip spanners

Metrics

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

References

  1. 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
  2. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, January 1993. URL: https://doi.org/10.1007/BF02189308.
  3. Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Improved approximation for the directed spanner problem. In International Colloquium on Automata, Languages, and Programming, pages 1-12, Berlin, Heidelberg, 2011. Springer. Google Scholar
  4. Piotr Berman, Sofya Raskhodnikova, and Ge Ruan. Finding sparser directed spanners. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 424-435, Dagstuhl, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.424.
  5. A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. Woodruff. Transitive-closure spanners. SIAM Journal on Computing, 41(6):1380-1425, 2012. URL: https://doi.org/10.1137/110826655.
  6. Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford. Improved Girth Approximation and Roundtrip Spanners. arXiv e-prints, page arXiv:1907.10779, July 2019. URL: http://arxiv.org/abs/1907.10779.
  7. Lenore J Cowen and Christopher G Wagner. Compact roundtrip routing for digraphs. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 885-886, Philadelphia, 1999. SIAM. Google Scholar
  8. Lenore J Cowen and Christopher G Wagner. Compact roundtrip routing in directed networks. In Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, pages 51-59, New York, 2000. ACM. Google Scholar
  9. Michael Dinitz and Robert Krauthgamer. Directed spanners via flow-based linear programs. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 323-332, New York, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993680.
  10. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Google Scholar
  11. Paul Erdös. Extremal problems in graph theory. In Theory of Graphs and Its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36, Prague, 1964. Publ. House Czechoslovak Acad. Sci. Google Scholar
  12. Michael L Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987. Google Scholar
  13. Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, and Virginia Vassilevska Williams. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1374-1392, Philadelphia, 2018. SIAM. Google Scholar
  14. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000. Google Scholar
  15. Sofya Raskhodnikova. Transitive-closure spanners: A survey. In Property Testing, pages 167-196. Springer, Berlin, Heidelberg, 2010. Google Scholar
  16. Liam Roditty, Mikkel Thorup, and Uri Zwick. Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms, 4(3):29:1-29:17, July 2008. URL: https://doi.org/10.1145/1367064.1367069.
  17. Mikkel Thorup and Uri Zwick. Approximate distance oracles. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 183-192, New York, 2001. ACM. Google Scholar
  18. Chun Jiang Zhu and Kam-Yiu Lam. Deterministic improved round-trip spanners. Information Processing Letters, 129:57-60, 2018. Google Scholar
  19. Uri Zwick. Exact and approximate distances in graphs: a survey. In European Symposium on Algorithms, pages 33-48, Berlin, Heidelberg, 2001. Springer. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact