A Linear-time Algorithm for Sparsification of Unweighted Graphs

Abstract

Given an undirected graph $G$ and an error parameter $\epsilon >0$, the {\em graph sparsification} problem requires sampling edges in $G$ and giving the sampled edges appropriate weights to obtain a sparse graph $G_{\epsilon }$ with the following property: the weight of every cut in $G_{\epsilon }$ is within a factor of $(1\pm \epsilon )$ of the weight of the corresponding cut in $G$. If $G$ is unweighted, an $O(m\log n)$-time algorithm for constructing $G_{\epsilon }$ with $O(n\log n/{\epsilon }^2)$ edges in expectation, and an $O(m)$-time algorithm for constructing $G_{\epsilon }$ with $O(n{\log }^{2}n/{\epsilon }^2)$ edges in expectation have recently been developed (Hariharan-Panigrahi, 2010). In this paper, we improve these results by giving an $O(m)$-time algorithm for constructing $G_{\epsilon }$ with $O(n\log n/{\epsilon }^2)$ edges in expectation, for unweighted graphs. Our algorithm is optimal in terms of its time complexity; further, no efficient algorithm is known for constructing a sparser $G_{\epsilon }$. Our algorithm is Monte-Carlo, i.e. it produces the correct output with high probability, as are all efficient graph sparsification algorithms.

References in corpus (1)

• A General Framework for Graph Sparsification