论文标题
接近线性尺寸的超图切割稀疏器
Near-linear Size Hypergraph Cut Sparsifiers
论文作者
论文摘要
图中的剪切是研究的基本对象，并且在图算法的研究中起着核心作用。大约保留其切割结构时稀疏图的问题已经进行了广泛的研究，并具有许多应用。 Benczúr和Karger（1996）在一项开创性的工作中表明，鉴于任何$ n $ vertex无方向的加权图$ g $和一个参数$ \ varepsilon \ in（0,1）$，有一个接近线性的时间算法，有一个重量$ g'因此，$ g $中的每个削减的重量都可以在$ g'$中的$（1 \ pm \ varepsilon）$中保存在$（1 \ pm \ varepsilon）之内。图$ g'$称为{\ em $（1 \ pm \ varepsilon）$ - $ g $的近似切割sparsifier}。 一个自然的问题是，是否还存在用于超图的这种剪裁的稀疏器。 Kogan and Krauthgamer（2015）提起了该问题的研究，并表明，鉴于每个Hyperdeed的基数为$ r $的任何加权超图$ h $，有一个多项式时算法，可以找到$（1 \ pm \ pm \ pm \ varepsilon）$ - 近似$ h $ h $ h $ h $ h $ h $ h $ h $ h $ $ \ tilde {o}（\ frac {nr} {\ varepsilon^2}）$。由于$ r $可以长达$ n $，因此，这给出了一个大小$ \ tilde {o}（n^2/\ varepsilon^2）$的超图切割的弹脚，这是一个比benczúr-karger bung的因子$ n $。 Benczúr-Karger BOND在HyperGraphs上是否可以实现。在这项工作中，我们通过提供一种新的多项式时间算法来解决这个问题，以创建大小$ \ tilde {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'$ 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'$. The graph $G'$ is referred to as a {\em $(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)$.
