Skip to main content

Graph Spanner

Problem Specification#

Input#

G=(V,E)G=(V, E), an undirected, unweighted graph, and an integer stretch factor, kk.

Output#

HEH \subseteq E, a set of edges such that for every u,vVu,v \in V connected in GG, distH(u,v)O(k)distG(u,v)\mathsf{dist}_{H}(u, v) \leq O(k) \cdot \mathsf{dist}_{G}(u,v).

Algorithm Implementations#

The algorithm is based on the Miller, Peng, Xu, and Vladu (MPXV) paper from SPAA'15 [1]. Our implementation is described in more detail in [2]. The code for our implemenation is available here.

The construction results in an O(k)O(k)-spanner with expected size O(n1+1/k)O(n^{1+1/k}).

Cost Bounds#

The algorithm runs in O(m)O(m) work and O(klogn)O(k\log n) depth w.h.p. More details about our implementation and the cost bounds can be found in Section 6.1 of [2].

Compiling and Running#

The benchmark can be compiled by running:

bazel build -c opt //benchmarks/Spanner/MPXV15:Spanner

It can then be run on a test input graph in the uncompressed format as follows:

numactl -i all ./bazel-bin/benchmarks/Spanner/MPXV15/Spanner_main -s -m -src 1 inputs/rMatGraph_J_5_100

It can then be run on a test input graph in the compressed format as follows:

numactl -i all ./bazel-bin/benchmarks/Spanner/MPXV15/Spanner_main -s -c -m -src 1 inputs/rMatGraph_J_5_100.bytepda

References#

[1] Gary L. Miller, Richard Peng, Adrian Vladu, Shen Chen Xu.
Improved Parallel Algorithms for Spanners and Hopsets.
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015.

[2] Laxman Dhulipala, Guy Blelloch, and Julian Shun
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 393-404, 2018.