Fully Dynamic Spectral Sparsification for Directed Hypergraphs

Sebastian Forster, Gramoz Goranci, Ali Momeni · 2025

Read Fully Dynamic Spectral Sparsification for Directed Hypergraphs by Sebastian Forster, Gramoz Goranci, Ali Momeni (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21671.txt.

Introduction

Sebastian Forster, Gramoz Goranci, and Ali Momeni maintain spectral sparsifiers for directed hypergraphs that keep changing. A sparsifier is a small stand-in that preserves a graph's essential spectral properties, letting algorithms run faster. Hypergraphs generalize graphs by letting one edge join many vertices, and directed hypergraphs add orientation. Real data changes constantly, so the sparsifier must update under insertions and deletions.

Their algorithm is fully dynamic and strikingly simple. It maintains a sparsifier whose size is near-optimal, growing with the square of the vertex count divided by the square of the accuracy parameter, times logarithmic factors. The amortized update time depends on the hypergraph's rank, the largest hyperedge size, again times logarithmic factors. They extend the method to the batch-dynamic parallel setting, where many changes arrive at once. It is the first spectral sparsification algorithm of its kind there.

Catalog record

CREATORSebastian Forster, Gramoz Goranci, Ali Momeni
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-21671

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fully Dynamic Spectral Sparsification for Directed Hypergraphs Sebastian Forster, Gramoz Goranci, Ali Momeni 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 directed hypergraphs. Our algorithm achieves a near-optimal size of O ⁡ ( n 2 / ε 2 ​ log 7 ​ m ) O(n^{2}/\varepsilon^{2}\log^{7}m) and amortized update time of O ⁡ ( r 2 ​ log 3 ​ m ) O(r^{2}\log^{3}m) , where n n is the number of vertices, and m m and r 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 k hyperedge insertions or deletions can be processed with O ⁡ ( k ​ r 2 ​ log 3 ​ m ) O(kr^{2}\log^{3}m) amortized work and O ⁡ ( log 2 ⁡ m ) O(\log^{2}m) depth. This constitutes the first spectral-based sparsification algorithm in this setting. 1 Introduction Sparsification–the process of approximating a graph with another that has fewer edges while preserving a key property–is a central paradigm in the design of efficient graph algorithms. A fundamental property of interest is graph cuts, which are not only foundational in graph theory and serve as duals to flows, but also have widespread applications in areas such as graph clustering [ LGT14 , PSZ17 , Fen18 ] and image segmentation [ BV06 , KT10 ] , to mention a few. In their seminal work, [ BK96 ] [ BK96 ] initiated the study of sparsifiers in the context of graph cuts. They showed that any graph admits a sparse reweighted cut-sparsifier whilst paying a small loss in the approximation. [ ST11 ] [ ST11 ] introduced a variant of sparsification known as spectral sparsification, which generalizes cut sparsification and measures graph similarity via the spectrum of their Laplacian matrices. The development of such sparsification techniques has had a profound impact across algorithm design [ Mad10 , She13 , ST14 , Pen16 ] , with the Laplacian paradigm standing out as a key example [ BHV08 , SS08 , DS08 , KM09 , KMT11 ] . Motivated by the need to capture complex interdependencies in real-world data, beyond the pairwise relationships modeled by traditional graphs, there has been a surge of interest in recent years in developing spectral sparsifiers for hypergraphs. These efforts have led to algorithmic constructions that achieve near-optimal size guarantees [ KKTY21 , KKTY21a , OST23 , JLS23 , Lee23 ] . However, a common limitation of these algorithms is the assumption that the input graph is static–an assumption that does not hold in many practical settings. For example, real-world graphs, such as those modeling social networks, are inherently dynamic and undergo continual structural changes. For undirected hypergraphs, this limitation has been addressed in two recent independent works [ GM25 , KLP25 ] , which show that spectral hypergraph sparsifiers can be maintained dynamically, supporting both hyperedge insertions and deletions in polylogarithmic time with respect to input parameters. This naturally leads to the question of whether directed hypergraphs also admit similarly efficient dynamic sparsification algorithms. In this paper, we study problems at the intersection of dynamic graph-based data structures and spectral sparsification for directed hypergraphs. Specifically, we consider the setting where a directed hypergraph undergoes hyperedge insertions and deletions, and the goal is to efficiently process these updates while maintaining a spectral sparsifier that approximates the input hypergraph. Our work builds upon variants of two key algorithmic constructions: the static spectral sparsification framework for directed hypergraphs developed by [ OST23 ] [ OST23 ] , and the dynamic sparsifier maintenance techniques for ordinary graphs by [ ADKKP16 ] [ ADKKP16 ] . Leveraging insights from both lines of work and modifying them to our setting, we design efficient dynamic algorithms for maintaining spectral sparsifiers of directed hypergraphs, as formalized in the theorem below. Theorem 1.1 . Given a directed hypergraph H=(V,E,\boldsymbol{w}) with n vertices, rank r , and at most m hyperedges (at any time), there is a fully dynamic data structure that, with high probability, maintains a (1\pm\varepsilon) -spectral hypersparsifier \widetilde{H} of H of size O(n^{2}/\varepsilon^{2}\log^{7}m) in O(r^{2}\log^{3}m) amortized update time. The guarantees provided by the above theorem are nearly tight, for the following reasons: (1) even reading the hyperedges in a hypergraph of rank r requires \Theta(r) time, which means any update time must inherently depend on r , and (2) in the setting of directed graphs, it is folklore that a complete bipartite graph on n vertices, with all edges directed from one partition to the other, gives an \Omega(n^{2}) lower bound on the size of any directed sparsifier. Moreover, [ OST23 ] [ OST23 ] established an even stronger lower bound, showing that any spectral sparsifier must also incur a \Omega(\epsilon^{-1}) dependence. The latter implies that the size of our dynamic sparsifier is optimal up to a factor of \epsilon^{-1} and polylogarithmic terms. Our algorithmic construction also extends naturally to the closely related batch-dynamic setting. In this model–similar to the fully dynamic setting–updates consist of hyperedge insertions and deletions, but are processed in batches, enabling the exploitation of parallelism. This approach is particularly well-suited for handling high-throughput update streams and may more accurately reflect how dynamic changes are managed in real-time systems. Our result in this model is formalized in the theorem below. Theorem 1.2 . Given a directed hypergraph H=(V,E,\boldsymbol{w}) with n vertices, rank r , and at most m hyperedges (at any time) undergoing batches of k hyperedge additions or deletions, there is a parallel fully dynamic data structure that, with high probability, maintains a (1\pm\varepsilon) -spectral hypersparsifier \widetilde{H} of H of size O(n^{2}/\varepsilon^{2}\log^{7}m) in O(kr^{2}\log^{3}m) amortized work and O(\log^{2}m) depth. 1.1 Related Work We briefly discuss the related work on graphs and hypergraphs for several computational models. Static Algorithms. Starting with [ ST11 ] , spectral sparsification has been extensively studed on graphs [ BSS12 , KP12 , BSST13 , ZLO15 , KLP16 , LS17 , LS18 ] . Recently, the concept has been extended to undirected and directed hypergraphs [ SY19 , BST19 , KKTY21 , KKTY21a , RY22 , OST23 , Lee23 , JLS23 , KPS24 ] . Dynamic Algorithms. For undirected graphs, there have been several results for dynamic cut sparsifiers that use a similar approach to ours. This includes [ ADKKP16 ] , which achieves polylogarithmic update time using t -bundle spanners, and its extension against an adaptive adversary by [ BBGNSSS22 ] and to directed graphs [ Zha25 ] . More recently, [ KLP25 ] achieved a fully dynamic spectral sparsifier with near-optimal size and update time for undirected hypergraphs. More broadly, spectral-based sparsification is closely related to dynamic vertex sparsifiers [ GHP18 , DGGP19 , CGHPS20 , GLP21 , AMV21 , BGJLLPS22 , DGGLPSY22 ] . Distributed and Parallel Algorithms. [ KX16 ] achieved simple yet powerful algorithms for spectral graph sparsification in both parallel and distributed settings. Very recently, [ GK25 ] developed a parallel batch-dynamic algorithm for spanners. Other related works include distributed vertex sparsifiers [ ZLB21 ,

Read the complete text