Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting
This work addresses a theoretical gap in graph sparsification for streaming settings, which is incremental as it fixes an existing analysis.
The paper tackled the flaw in the original analysis of Kelner and Levin's incremental resparsification algorithm by deriving a new proof using martingale inequalities to rigorously account for dependencies across resparsifications, showing it produces a spectral sparsifier with high probability.
We derive a new proof to show that the incremental resparsification algorithm proposed by Kelner and Levin (2013) produces a spectral sparsifier in high probability. We rigorously take into account the dependencies across subsequent resparsifications using martingale inequalities, fixing a flaw in the original analysis.