Fully Dynamic Spectral Sparsification for Directed Hypergraphs

There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of $\mathit{\text{directed}}$ hypergraphs. Our algorithm achieves a near-optimal size of $O(n^2\mathrm{/}{\epsilon }^2{\log }^{7}m)$ and amortized update time of $O(r^2{\log }^{3}m)$, where $n$ is the number of vertices, and $m$ and $r$ respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any $k$ hyperedge insertions or deletions can be processed with $O(k{r}^2{\log }^{3}m)$ amortized work and $O({\log }^{2}m)$ depth. This constitutes the first spectral-based sparsification algorithm in this setting.