2026-09-22T20:10:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25527 2026-09-05T19:19:23Z ddc:004 open_access

Fully Dynamic Spectral Sparsification for Directed Hypergraphs Forster, Sebastian Goranci, Gramoz Momeni, Ali Spectral sparsification Dynamic algorithms (Directed) hypergraphs Data structures 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 directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ 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² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Forster and Gramoz Goranci and Ali Momeni 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.38 urn:nbn:de:0030-drops-255272 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.38 eng https://creativecommons.org/licenses/by/4.0/legalcode