2022/09/16 by Chen, Yu, Khanna, Sanjeev, Li, Huan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2209.07729
A seminal work of [Ahn-Guha-McGregor, PODS'12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS'14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA'21]. All these linear sketching algorithms, however, only work on unweighted graphs. In this paper, we initiate the study of weighted graph sparsification by linear sketching by investigating a natural class of linear sketches that we call incidence sketches, in which each measurement is a linear combination of the weights of edges incident on a single vertex. Our results are: 1. Weighted cut sparsification: We give an algorithm that computes a (1 + ε)-cut sparsifier using O(n ε-3) linear measurements, which is nearly optimal. 2. Weighted spectral sparsification: We give an algorithm that computes a (1 + ε)-spectral sparsifier using O(n6/5 ε-4) linear measurements. Complementing our algorithm, we then prove a superlinear lower bound of Ω(n21/20-o(1)) measurements for computing some O(1)-spectral sparsifier using incidence sketches. 3. Weighted spanner computation: We focus on graphs whose largest/smallest edge weights differ by an O(1) factor, and prove that, for incidence sketches, the upper bounds obtained by~[Filtser-Kapralov-Nouri, SODA'21] are optimal up to an no(1) factor.