TY - GEN

T1 - Constructing light spanners deterministically in near-linear time

AU - Alstrup, Stephen

AU - Dahlgaard, Søren

AU - Filtser, Arnold

AU - Stöckel, Morten

AU - Wulff-Nilsen, Christian

PY - 2019

Y1 - 2019

N2 - Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [11] improved the state-of-the-art for light spanners by constructing a (2k − 1)(1 + ε)-spanner with O(n1+1/k) edges and Oε(n1/k) lightness. Soon after, Filtser and Solomon [19] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O(mn1+1/k) (which is faster than [11]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Ωε(kn1/k), even when randomization is used. The contribution of this paper is deterministic spanner constructions that are fast, and achieve similar bounds as the state-of-the-art slower constructions. Our first result is an Oε(n2+1/k+ε') time spanner construction which achieves the state-of-the-art bounds. Our second result is an Oε(m + n log n) time construction of a spanner with (2k − 1)(1 + ε) stretch, O(log k · n1+1/k) edges and Oε(log k · n1/k) lightness. This is an exponential improvement in the dependence on k compared to the previous result with such running time. Finally, for the important special case where k = log n, for every constant ε > 0, we provide an O(m + n1+ε) time construction that produces an O(log n)-spanner with O(n) edges and O(1) lightness which is asymptotically optimal. This is the first known sub-quadratic construction of such a spanner for any k = ω(1). To achieve our constructions, we show a novel deterministic incremental approximate distance oracle. Our new oracle is crucial in our construction, as known randomized dynamic oracles require the assumption of a non-adaptive adversary. This is a strong assumption, which has seen recent attention in prolific venues. Our new oracle allows the order of the edge insertions to not be fixed in advance, which is critical as our spanner algorithm chooses which edges to insert based on the answers to distance queries. We believe our new oracle is of independent interest.

AB - Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [11] improved the state-of-the-art for light spanners by constructing a (2k − 1)(1 + ε)-spanner with O(n1+1/k) edges and Oε(n1/k) lightness. Soon after, Filtser and Solomon [19] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O(mn1+1/k) (which is faster than [11]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Ωε(kn1/k), even when randomization is used. The contribution of this paper is deterministic spanner constructions that are fast, and achieve similar bounds as the state-of-the-art slower constructions. Our first result is an Oε(n2+1/k+ε') time spanner construction which achieves the state-of-the-art bounds. Our second result is an Oε(m + n log n) time construction of a spanner with (2k − 1)(1 + ε) stretch, O(log k · n1+1/k) edges and Oε(log k · n1/k) lightness. This is an exponential improvement in the dependence on k compared to the previous result with such running time. Finally, for the important special case where k = log n, for every constant ε > 0, we provide an O(m + n1+ε) time construction that produces an O(log n)-spanner with O(n) edges and O(1) lightness which is asymptotically optimal. This is the first known sub-quadratic construction of such a spanner for any k = ω(1). To achieve our constructions, we show a novel deterministic incremental approximate distance oracle. Our new oracle is crucial in our construction, as known randomized dynamic oracles require the assumption of a non-adaptive adversary. This is a strong assumption, which has seen recent attention in prolific venues. Our new oracle allows the order of the edge insertions to not be fixed in advance, which is critical as our spanner algorithm chooses which edges to insert based on the answers to distance queries. We believe our new oracle is of independent interest.

KW - Deterministic dynamic distance oracle

KW - Efficient construction

KW - Light spanners

KW - Spanners

UR - http://www.scopus.com/inward/record.url?scp=85074848353&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2019.4

DO - 10.4230/LIPIcs.ESA.2019.4

M3 - Article in proceedings

AN - SCOPUS:85074848353

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 27th Annual European Symposium on Algorithms, ESA 2019

A2 - Bender, Michael A.

A2 - Svensson, Ola

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th Annual European Symposium on Algorithms, ESA 2019

Y2 - 9 September 2019 through 11 September 2019

ER -