A framework for analyzing resparsification algorithms

DOI10.1137/1.9781611974782.132zbMATH Open1410.05205arXiv1611.06940OpenAlexW2950542405MaRDI QIDQ4575880FDOQ4575880

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)

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.

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

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

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)

Cited In (9)

• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• 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
• Title not available (Why is that?)
• Spectral sparsification in the semi-streaming setting
• A combinatorial cut-toggling algorithm for solving Laplacian linear systems

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)