论文标题
通过简单的迭代采样算法对定向超图的几乎紧密的光谱稀疏
Nearly Tight Spectral Sparsification of Directed Hypergraphs by a Simple Iterative Sampling Algorithm
论文作者
论文摘要
在过去的几年中，已广泛研究了将众所周知的光谱图稀疏延伸到超图的尝试。对于无方向的超图，Kapralov，Krauthgamer，Tardos和Yoshida〜（2022）已被证明是$ \ varepsilon $ -spectral sparsifier of Optimal $ o^*（n）$ size的Spectral Sparsifier，其中$ n $是$ o^*$ pertices and $ o^*$ pogs $ \ vareps $ n $ \ n $ \ n $ im \ y;但是，对于定向的超图，最佳的稀疏器尺寸尚不清楚。我们的主要贡献是第一种构建$ o^*（n^2）$ - 尺寸$ \ varepsilon $ -Spectral Sparsifier的算法，用于加权定向超图。我们的结果是最佳的，直至$ \ varepsilon^{ - 1} $和$ \ log n $因子，因为即使在有向图的情况下也有$ω（n^2）$的下限。我们还显示了通用定向超图的$ω（n^2/\ varepsilon）$的第一个非平凡的下限。我们的算法的基本思想是从Koutis and Xu〜（2016）的基于扳手的普通图基于扳手的稀疏中借来的。他们的迭代抽样方法确实对于在各种情况下设计稀疏算法确实很有用。为了证明这一点，我们还为无方向的超图提供了类似的迭代采样算法，该算法达到了最佳尺寸界限之一，享受平行实现，并且可以转化为容忍故障。
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 $Ω(n^2)$ even for directed graphs. We also show the first non-trivial lower bound of $Ω(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~(2016). 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.
