标题： 完全动态的超图谱稀疏化 显示英文标题

标题： Fully Dynamic Spectral Sparsification of Hypergraphs

摘要： 谱超图稀疏化是已广泛研究的图谱稀疏化概念的自然推广，近年来已成为深入研究的主题。 在本工作中，我们考虑动态设置下的谱超图稀疏化，其中目标是在一系列超边插入和删除的情况下维护一个无向加权超图的谱稀疏化器。 对于任何$0 < \varepsilon \leq 1$，我们给出了维护大小为$ n r^3 \operatorname{poly}\left( \log n, \varepsilon ^{-1} \right) $的$ (1 \pm \varepsilon) $-谱超图稀疏化器的第一个完全动态算法，其摊销更新时间为$ r^4 \operatorname{poly}\left( \log n, \varepsilon ^{-1} \right) $，其中$n$是底层超图的顶点数，$r$是超边秩的一个上界。 我们的主要贡献是证明 Koutis 和 Xu（2016）的基于跨度的稀疏化算法在超图设置中可以动态实现，从而扩展了 Abraham 等人（2016）的普通图动态谱稀疏化框架。 显示英文摘要

摘要： Spectral hypergraph sparsification, a natural generalization of the well-studied spectral sparsification notion on graphs, has been the subject of intensive research in recent years. In this work, we consider spectral hypergraph sparsification in the dynamic setting, where the goal is to maintain a spectral sparsifier of an undirected, weighted hypergraph subject to a sequence of hyperedge insertions and deletions. For any $0 < \varepsilon \leq 1$, we give the first fully dynamic algorithm for maintaining an $ (1 \pm \varepsilon) $-spectral hypergraph sparsifier of size $ n r^3 \operatorname{poly}\left( \log n, \varepsilon ^{-1} \right) $ with amortized update time $ r^4 \operatorname{poly}\left( \log n, \varepsilon ^{-1} \right) $, where $n$ is the number of vertices of the underlying hypergraph and $r$ is an upper-bound on the rank of hyperedges. Our key contribution is to show that the spanner-based sparsification algorithm of Koutis and Xu (2016) admits a dynamic implementation in the hypergraph setting, thereby extending the dynamic spectral sparsification framework for ordinary graphs by Abraham et al. (2016).