Near-linear Size Hypergraph Cut Sparsifiers

摘要: Cuts in graphs are a fundamental object of study, and play central role the study graph algorithms. The problem sparsifying while approximately preserving its cut structure has been extensively studied many applications. In seminal work, Benczur Karger (1996) showed that given any $n$ -vertex undirected weighted $G$ parameter $\varepsilon\in(0,1)$ , there is near-linear time algorithm outputs subgraph $G^{\prime}$ size $\tilde{O}(n/\varepsilon^{2})$ such weight every preserved to within ( $1\pm\varepsilon$ )-factor . referred as )-approximate sparsifier A natural question if cut-preserving sparsifiers also exist for hypergraphs. Kogan Krauthgamer (2015) initiated this hypergraph $H$ where cardinality each hyperedge bounded by $r$ polynomial-time find $\tilde{O}(\frac{nr}{\varepsilon^{2}})$ Since can be large general, gives $\tilde{O}(n^{2}/\varepsilon^{2})$ which factor larger than Benczur-Karger bound graphs. It an open whether or not achievable on we resolve affirmative giving new creating