# Near-Optimal Spanners for General Graphs in (Nearly) Linear Time

Hung Le., Shay Solomon

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

## Abstract

Let G = (V, E, w) be a weighted undirected graph on |V| = n vertices and |E| = m edges, let k ≥ 1 be any integer, and let ? < 1 be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness,1 which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdos' girth conjecture and disregarding the ?-dependencies.) There are (deterministic) algorithms for constructing (2k-1)(1 + ?)-spanners for G with a near-optimal sparsity of O(n1/k · log(1/?)/?)). The first algorithm can be implemented in the pointer-machine model within time O(mα(m, n) · log(1/?)/?)+ SORT(m)), where α(·,·) is the two-parameter inverse-Ackermann function and SORT(m) is the time needed to sort m integers. The second algorithm can be implemented in the Word RAM model within time O(m log(1/?)/?)). There is a (deterministic) algorithm for constructing a (2k-1)(1 + ?)-spanner for G that achieves a near-optimal bound of O(n1/k ·poly(1/?)) on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time O(mα(m,n) · poly(1/?) + SORT(m)) and in the Word RAM model within time O(mα(m,n) · poly(1/?)). The previous fastest constructions of (2k-1)(1 + ?)-spanners with near-optimal sparsity incur a runtime of is O(min{m(n1+1/k) + n log n, k · n2+1/k}), even regardless of the lightness. Importantly, the greedy spanner for stretch 2k-1 has sparsity O(n1/k) - with no ?-dependence whatsoever, but its runtime is O(m(n1+1/k + n log n)). Moreover, the state-of-the-art lightness bound of any (2k-1)-spanner (including the greedy spanner) is poor, even regardless of the sparsity and runtime.

Original language English ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 Association for Computing Machinery 3332-3361 30 9781611977073 Published - 2022 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United StatesDuration: 9 Jan 2022 → 12 Jan 2022

### Publication series

Name Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 2022-January

### Conference

Conference 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 United States Alexander 9/01/22 → 12/01/22

## Fingerprint

Dive into the research topics of 'Near-Optimal Spanners for General Graphs in (Nearly) Linear Time'. Together they form a unique fingerprint.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8285784,"math_prob":0.84516376,"size":4084,"snap":"2023-40-2023-50","text_gpt3_token_len":1180,"char_repetition_ratio":0.11446078,"word_repetition_ratio":0.84639496,"special_character_ratio":0.29456416,"punctuation_ratio":0.12879708,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9730402,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-01T16:39:43Z\",\"WARC-Record-ID\":\"<urn:uuid:2261a76f-9963-41ba-9dd2-691948f9d7ba>\",\"Content-Length\":\"50292\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a4691f7a-401d-43b2-afa0-f6600092fa39>\",\"WARC-Concurrent-To\":\"<urn:uuid:6e41cfbf-a7b7-4241-8caa-6500af4a8282>\",\"WARC-IP-Address\":\"34.253.178.11\",\"WARC-Target-URI\":\"https://cris.tau.ac.il/en/publications/near-optimal-spanners-for-general-graphs-in-nearly-linear-time\",\"WARC-Payload-Digest\":\"sha1:TA2CDTLOJDPU6K3CMQ4GGTK4MQAOZBA7\",\"WARC-Block-Digest\":\"sha1:K2VNAUJ2557FLPV5GGGO6EEQNLW2COYM\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100290.24_warc_CC-MAIN-20231201151933-20231201181933-00306.warc.gz\"}"}