2020/07/28 by Arnold Filtser, Filtser, Arnold, Michael Kapralov +3 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2007.14204
openalex publication_date 2020/07/28 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Graph sketching is a powerful technique introduced by the seminal work of\nAhn, Guha and McGregor'12 on connectivity in dynamic graph streams that has\nenjoyed considerable attention in the literature since then, and has led to\nnear optimal dynamic streaming algorithms for many fundamental problems such as\nconnectivity, cut and spectral sparsifiers and matchings. Interestingly,\nhowever, the sketching and dynamic streaming complexity of approximating the\nshortest path metric of a graph is still far from well-understood. Besides a\ndirect k-pass implementation of classical spanner constructions (recently\nimproved to lfloor frac k2 rfloor+1-passes by Fernandez, Woodruff and\nYasuda'20) the state of the art amounts to a O(\log k)-pass algorithm of Ahn,\nGuha and McGregor'12, and a 2-pass algorithm of Kapralov and Woodruff'14. In\nparticular, no single pass algorithm is known, and the optimal tradeoff between\nthe number of passes, stretch and space complexity is open.\n In this paper we introduce several new graph sketching techniques for\napproximating the shortest path metric of the input graph. We give the first\n em single pass sketching algorithm for constructing graph spanners: we show\nhow to obtain a widetildeO(n frac23)-spanner using widetildeO(n)\nspace, and in general a widetildeO(n frac23(1-\α))-spanner using\n widetildeO(n1+\α) space for every \α\∈ [0, 1], a tradeoff\nthat we think may be close optimal. We also give new spanner construction\nalgorithms for any number of passes, simultaneously improving upon all prior\nwork on this problem. Finally, we study the simultaneous communication model\nand propose the first protocols with low per player information.\n