An SDP-based algorithm for linear-sized spectral sparsification

DOI10.1145/3055399.3055477MaRDI QIDQ4978013zbMATH OpenOpenAlexFDO

Authors Yin Tat Lee, He Sun

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

spectral graph theoryspectral sparsification

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: For any undirected and weighted graph $G=(V,E,w)$ with $n$ vertices and $m$ edges, we call a sparse subgraph $H$ of $G$, with proper reweighting of the edges, a $(1+varepsilon)$-spectral sparsifier if [ (1-varepsilon)x^{intercal}L_Gxleq x^{intercal} L_{H} xleq (1+varepsilon) x^{intercal} L_Gx ] holds for any $xinmathbb{R}^n$, where $L_G$ and $L_H$ are the respective Laplacian matrices of $G$ and $H$. Noticing that $Omega(m)$ time is needed for any algorithm to construct a spectral sparsifier and a spectral sparsifier of $G$ requires $Omega(n)$ edges, a natural question is to investigate, for any constant $varepsilon$, if a $(1+varepsilon)$-spectral sparsifier of $G$ with $O(n)$ edges can be constructed in $ildeO(m)$ time, where the $ildeO$ notation suppresses polylogarithmic factors. All previous constructions on spectral sparsification require either super-linear number of edges or $m^{1+Omega(1)}$ time. In this work we answer this question affirmatively by presenting an algorithm that, for any undirected graph $G$ and $varepsilon>0$, outputs a $(1+varepsilon)$-spectral sparsifier of $G$ with $O(n/varepsilo{n}^2)$ edges in $ildeO(m/varepsilo{n}^{O(1)})$ time. Our algorithm is based on three novel techniques: (1) a new potential function which is much easier to compute yet has similar guarantees as the potential functions used in previous references; (2) an efficient reduction from a two-sided spectral sparsifier to a one-sided spectral sparsifier; (3) constructing a one-sided spectral sparsifier by a semi-definite program.

Recommendations

• Constructing linear-sized spectral sparsification in almost-linear time
• Spectral sparsification of graphs
• Faster spectral sparsification and numerical algorithms for SDD matrices
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Graph sparsification by effective resistances

Cited in

(29)

• Faster cut sparsification of weighted graphs
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• Spectral sparsification of graphs
• Spectral sparsification in the semi-streaming setting
• Minimum cuts and sparsification in hypergraphs
• Constructing linear-sized spectral sparsification in almost-linear time
• Twice-Ramanujan sparsifiers
• Sparse sums of positive semidefinite matrices
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• A Spectral Approach to Network Design
• Evolution of the diffusion-induced flow over a disk, submerged in a stratified viscous fluid
• Twice-Ramanujan sparsifiers
• Twice-Ramanujan sparsifiers
• Spectral sparsification of hypergraphs
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• Graph sparsification by effective resistances
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Randomized least-squares with minimal oversampling and interpolation in general spaces
• Spectral sparsification via bounded-independence sampling
• Better sparsifiers for directed Eulerian graphs
• Eldan's stochastic localization and the KLS conjecture: isoperimetry, concentration and mixing
• Small-space spectral sparsification via bounded-independence sampling
• Sparsification of directed graphs via cut balance
• Sublinear time hypergraph sparsification via cut and edge sampling queries
• Decremental (1+)-approximate maximum eigenvector: dynamic power method
• Faster spectral sparsification and numerical algorithms for SDD matrices

This page was built for publication: An SDP-based algorithm for linear-sized spectral sparsification

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