A framework for analyzing resparsification algorithms

DOI10.1137/1.9781611974782.132MaRDI QIDQ4575880zbMATH OpenOpenAlexFDO

Authors Rasmus Kyng, Jakub W. Pachocki, Richard Peng, Sushant Sachdeva

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06940

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Data structures (68P05) Density (toughness, etc.) (05C42)

Abstract: A spectral sparsifier of a graph $G$ is a sparser graph $H$ that approximately preserves the quadratic form of $G$, i.e. for all vectors $x$, $x^T{L}_{G}xapprox{x}^T{L}_{H}x$, where $L_G$ and $L_H$ denote the respective graph Laplacians. Spectral sparsifiers generalize cut sparsifiers, and have found many applications in designing graph algorithms. In recent years, there has been interest in computing spectral sparsifiers in semi-streaming and dynamic settings. Natural algorithms in these settings often involve repeated sparsification of a graph, and accumulation of errors across these steps. We present a framework for analyzing algorithms that perform repeated sparsifications that only incur error corresponding to a single sparsification step, leading to better results for many resparsification-based algorithms. As an application, we show how to maintain a spectral sparsifier in the semi-streaming setting: We present a simple algorithm that, for a graph $G$ on $n$ vertices and $m$ edges, computes a spectral sparsifier of $G$ with $O(nlogn)$ edges in a single pass over $G$, using only $O(nlogn)$ space, and $O(mlo{g}^{2}n)$ total time. This improves on previous best semi-streaming algorithms for both spectral and cut sparsifiers by a factor of $logn$ in both space and runtime. The algorithm extends to semi-streaming row sampling for general PSD matrices. We also use our framework to combine a spectral sparsification algorithm by Koutis with improved spanner constructions to give a parallel algorithm for constructing $O(nlo{g}^{2}nloglogn)$ sized spectral sparsifiers in $O(mlo{g}^{2}nloglogn)$ time. This is the best known combinatorial graph sparsification algorithm.The size of the sparsifiers is only a factor $lognloglogn$ more than ones produced by numerical routines.

Recommendations

• Spectral sparsification in the semi-streaming setting
• Spectral sparsification in the semi-streaming setting
• Single pass spectral sparsification in dynamic streams
• Spectral sparsification in dynamic graph streams
• Graph Sparsification in the Semi-streaming Model

Cited in

(9)

• A combinatorial cut-toggling algorithm for solving Laplacian linear systems
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Spectral sparsification in dynamic graph streams
• Single pass spectral sparsification in dynamic streams
• Graph Sparsification in the Semi-streaming Model
• Density independent algorithms for sparsifying \(k\)-step random walks
• scientific article; zbMATH DE number 7650109 (Why is no real title available?)
• Spectral sparsification in the semi-streaming setting

This page was built for publication: A framework for analyzing resparsification algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575880)