Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
复制标题
DOI：
10.4230/lipics.icalp.2021.53
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Yu Chen;S. Khanna;Ansh Nagda
中科院分区：
文献类型：
--
作者：
Yu Chen;S. Khanna;Ansh Nagda
大约保留其切割结构的同时稀疏图或超图的问题已经进行了广泛的研究，并具有许多应用。在开创性的工作中，Bencz \'Ur和Karger（1996）表明，鉴于任何$ n $ vertex无方向的加权图$ g $和一个参数$ \ varepsilon \ in（0,1）$输出加权子图$ g'$ g $ g $的时间算法$ \ tilde {o}（n/\ varepsilon^2）$，使得$ g $中的每个切割的权重都保留在$（$ g）之内（ 1 \ pm \ varepsilon）$ - 因子$ g'$。图$ g'$称为{\ em $（1 \ pm \ varepsilon）$ - $ g $的近似切割sparsifier}。随后的最近工作，对于更普遍的超透明率稀疏器问题也获得了类似的结果。但是，所有已知的稀疏算法都需要$ \ omega（n + m）$时间，其中$ n $表示顶点的数量和$ m $表示超图中的Hyperedges数量。由于$ m $在$ n $中可能是指数级的，所以一个自然的问题是，是否可以在$ n $中创建超图形的散布符，{\ em {\ em独立于边缘数}。我们以肯定的方式解决了这个问题，给出了对超图的适当查询访问，为此问题提供了第一个sublinear时间算法。
The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz\'ur 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$. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require $\Omega(n + m)$ time where $n$ denotes the number of vertices and $m$ denotes the number of hyperedges in the hypergraph. Since $m$ can be exponentially large in $n$, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in $n$, {\em independent of the number of edges}. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph.