{"ID":2825236,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.21671","arxiv_id":"2512.21671","title":"Fully Dynamic Spectral Sparsification for Directed Hypergraphs","abstract":"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 \\textit{directed} hypergraphs. Our algorithm achieves a near-optimal size of $O(n^2 / \\varepsilon ^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(kr^2 \\log ^3 m)$ amortized work and $O(\\log ^2 m)$ depth. This constitutes the first spectral-based sparsification algorithm in this setting.","short_abstract":"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 \\textit{directed} hypergraphs. Our algorithm achieves a near-optimal siz...","url_abs":"https://arxiv.org/abs/2512.21671","url_pdf":"https://arxiv.org/pdf/2512.21671v2","authors":"[\"Sebastian Forster\",\"Gramoz Goranci\",\"Ali Momeni\"]","published":"2025-12-25T13:31:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}