论文标题
通过扩展器分解的低级别超图中的连通性更快
Faster connectivity in low-rank hypergraphs via expander decomposition
论文作者
论文摘要
我们设计了一种用于计算超图中连接性的算法，该算法在时间上运行$ \ hat o_r（p + \ \ \ {λ^{λ^{\ frac {r-3} {r-3} {r-1} {r-1}} n^2，n^r/λ^{r/λ^{r/（r-1）}仅取决于$ r $）的主要参数和项，其中$ p $是大小，$ n $是顶点的数量，而$ r $是HyperGraph的等级。当等级恒定并且连接性$λ$为$ω（1）$时，我们的算法比现有算法快。我们算法的核心是简单超图中最小切割的结构性结果。我们显示了在所有最小切割中参与的Hyperedges数量与最小切割较小侧的大小之间的权衡。该结构结果可以看作是简单图的众所周知的结构定理的概括[Kawarabayashi-Thorup，jacm 19]。我们将扩展器分解的框架扩展到简单的超图，以证明这种结构性结果。我们还提供了结构性结果的证明，以获得我们更快的HyperGraph连接算法。
We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min\{λ^{\frac{r-3}{r-1}} n^2, n^r/λ^{r/(r-1)}\})$ (the $\hat O_r(\cdot)$ hides the terms subpolynomial in the main parameter and terms that depend only on $r$) where $p$ is the size, $n$ is the number of vertices, and $r$ is the rank of the hypergraph. Our algorithm is faster than existing algorithms when the the rank is constant and the connectivity $λ$ is $ω(1)$. At the heart of our algorithm is a structural result regarding min-cuts in simple hypergraphs. We show a trade-off between the number of hyperedges taking part in all min-cuts and the size of the smaller side of the min-cut. This structural result can be viewed as a generalization of a well-known structural theorem for simple graphs [Kawarabayashi-Thorup, JACM 19]. We extend the framework of expander decomposition to simple hypergraphs in order to prove this structural result. We also make the proof of the structural result constructive to obtain our faster hypergraph connectivity algorithm.
