Nearly Tight Spectral Sparsification of Directed Hypergraphs by a Simple Iterative Sampling Algorithm

Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirected hypergraphs, Kapralov, Krauthgamer, Tardos, and Yoshida (2022) have proved an $$\varepsilon $$ -spectral sparsifier of the optimal $$O^*(n)$$ size, where n is the number of vertices and $$O^*$$ suppresses the $$\varepsilon ^{-1}$$ and $$\log n$$ factors. For directed hypergraphs, however, the optimal sparsifier size has not been known. Our main contribution is the first algorithm that constructs an $$O^*(n^2)$$ -size $$\varepsilon $$ -spectral sparsifier for a weighted directed hypergraph. Our result is optimal up to the $$\varepsilon ^{-1}$$ and $$\log n$$ factors since there is a lower bound of $$\Omega (n^2)$$ even for directed graphs. We also show the first non-trivial lower bound of $$\Omega (n^2/\varepsilon )$$ for general directed hypergraphs. The basic idea of our algorithm is borrowed from the spanner-based sparsification for ordinary graphs by Koutis and Xu [30]. Their iterative sampling approach is indeed useful for designing sparsification algorithms in various circumstances. To demonstrate this, we also present a similar iterative sampling algorithm for undirected hypergraphs that attains one of the best size bounds, enjoys parallel implementation, and can be transformed to be fault-tolerant.