Near-linear Size Hypergraph Cut Sparsifiers
Near-linear Size Hypergraph Cut Sparsifiers
复制标题
DOI：
10.1109/focs46700.2020.00015
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Yu Chen;S. Khanna;Ansh Nagda
中科院分区：
文献类型：
--
作者：
Yu Chen;S. Khanna;Ansh Nagda
图中的割是一个基本的研究对象，在图算法的研究中起着核心作用。图的稀疏化问题已经得到了广泛的研究并得到了广泛的应用。在一项开创性的工作中，Benczúr和Karger(1996)证明了给定任意$n点无向赋权图$G和(0，1)$中的参数$varepsilon，存在一个近线性时间算法，它输出一个大小为$O}(n/varepsilon^{2})$G$的加权子图$G^{素数}$，使得$G$中的每个割的权重都保持在$G^{素数}$中的($1\pm\varepsilon$)因子内。图$G^{素数}$称为$G$的($1\pm\varepsilon$)-近似割稀疏子。一个自然的问题是，超图是否也存在这样的保割稀疏子。Kogan和KrauthGamer(2015)开始了对这个问题的研究，并证明了给定任何一个赋权超图$H$，其中每个超边的基数由$r$有界，则存在一个多项式时间算法来寻找大小为${O}(FRAC{nr}{\varepsilon^{2}})的$H$的($1\pm\varepsilon$)近似割稀疏器。由于$r$可以大到$n$，一般地，这给出了一个大小为$\tide{O}(n^{2}/\varepsilon^{2})$的超图割稀疏器，它是比图的Benczúr-Karger界大$n$的因子。Benczúr-Karger界在超图上是否可达一直是一个悬而未决的问题。在这项工作中，我们肯定地解决了这个问题，给出了一个新的多项式时间算法来生成大小为$\tide{O}(n/\varepsilon^{2})$的超图稀疏子。
Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any $n$-vertex undirected weighted graph $G$ and a parameter $\varepsilon\in(0,1)$, there is a near-linear time algorithm that outputs a weighted subgraph $G^{\prime}$ of $G$ of size $\tilde{O}(n/\varepsilon^{2})$ such that the weight of every cut in $G$ is preserved to within a ($1\pm\varepsilon$)-factor in $G^{\prime}$. The graph $G^{\prime}$ is referred to as a ($1\pm\varepsilon$)-approximate cut sparsifier of $G$. A natural question is if such cut-preserving sparsifiers also exist for hypergraphs. Kogan and Krauthgamer (2015) initiated a study of this question and showed that given any weighted hypergraph $H$ where the cardinality of each hyperedge is bounded by $r$, there is a polynomial-time algorithm to find a ($1\pm\varepsilon$)-approximate cut sparsifier of $H$ of size $\tilde{O}(\frac{nr}{\varepsilon^{2}})$. Since $r$ can be as large as $n$, in general, this gives a hypergraph cut sparsifier of size $\tilde{O}(n^{2}/\varepsilon^{2})$, which is a factor $n$ larger than the Benczúr-Karger bound for graphs. It has been an open question whether or not Benczúr-Karger bound is achievable on hypergraphs. In this work, we resolve this question in the affirmative by giving a new polynomial-time algorithm for creating hypergraph sparsifiers of size $\tilde{O}(n/\varepsilon^{2})$.