تقرير
Faster connectivity in low-rank hypergraphs via expander decomposition
| العنوان: | Faster connectivity in low-rank hypergraphs via expander decomposition |
|---|---|
| المؤلفون: | Beideman, Calvin, Chandrasekaran, Karthekeyan, Mukhopadhyay, Sagnik, Nanongkai, Danupon |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, F.2 |
| الوصف: | We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min\{\lambda^{\frac{r-3}{r-1}} n^2, n^r/\lambda^{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 $\lambda$ is $\omega(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. Comment: Incorporated a new algorithm of Chekuri and Quanrud into our algorithm and analysis. Fixed a bug in the analysis of the algorithm, and edited exposition throughout for greater clarity |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2011.08097 |
| رقم الأكسشن: | edsarx.2011.08097 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |