Online Algorithms for Spectral Hypergraph Sparsification

Abstract

We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an $(\epsilon ,\delta )$-spectral sparsifier with multiplicative error $\epsilon$ and additive error $\delta$ that has $O({\epsilon }^{-2}n\log n\log r\log (1+\epsilon W/\delta n))$ hyperedges with high probability, where $\epsilon ,\delta \in (0,1)$, $n$ is the number of nodes, and $W$ is the sum of edge weights. The space complexity of our algorithm is $O(n^2)$, while previous algorithms require the space complexity of $\Omega (m)$, where $m$ is the number of hyperedges. This provides an exponential improvement in the space complexity since $m$ can be exponential in $n$.

Improved the number of hyperedges from the previous version