Problem 91: Cut-Sparsification of Hypergraphs
| Suggested by | Robert Krauthgamer |
|---|---|
| Source | Warwick 2018 |
| Short link | https://sublinear.info/91 |
Informally, a cut-sparsifier of a hypergraph $H$ is a sparse hypergraph $H'$ on the same vertex set, whose cuts approximate those of $H$. The two “competing” quantities are the approximation factor and the size of the sparsifier $H'$ (for worst-case hypergraph $H$ on $n$ vertices). More formally, Let $H=(V,E,w)$ be an edge-weighted hypergraph. The weight of the cut $(S,\bar S)$ (i.e., for nontrivial $S\subset V$) is defined as $$ w_H(S,\bar S) := \sum_{e\in E: e\cap S\neq\emptyset, e\cap\bar S \neq\emptyset} w(e) . $$ A $(1+\epsilon)$-cut-sparsifier of $H$ is a hypergraph $H'=(V,E',w')$ (on the same vertex-set) such that $$ \forall S\subset V, \qquad w_{H'}(S,\bar S) \in (1\pm\epsilon) w_H(S,\bar S) . $$
Question: Is it true that for every $n$-vertex hypergraph $H$ and every $\epsilon\in (0,1/2)$, there is a $(1+\epsilon)$-cut-sparsifier $H'$ with at most $O(n/\epsilon^2)$ edges?
Upper bound: The known bound is $O(n^2/\epsilon^2)$ due to Kogan and Krauthgamer [KoganK-15]. It is based on the sparsification method of Benczur and Karger [BenczurK-96]. Another proof can be derived from a paper of Newman and Rabinovich [NewmanR-13].
Special cases: The current upper bound $O(n^2/\epsilon^2)$ can be refined in terms of $\rank(H) := \max_{e\in E} |e| \leq n$. When $\rank(H)=2$ (i.e., ordinary graphs where all edges have cardinality 2), there always exists a sparsifier $H'$ of size $O(n/\epsilon^2)$ [BatsonSS-14]. This bound easily extends to $\rank(H)=3$, because every hyperedge in $H$ can be replaced by a triangle (3 edges of cardinality 2) with edge weights $1/2$. For intermediate values of $\rank(H)$, the known upper bound is $O((\rank(H)+\log n) n/\epsilon^2)$ [KoganK-15]. Another family of hypergraphs that admits an improved bound is when for every two vertices $u,v\in V$, there is at most one edge $e\in E$ containing both $u$ and $v$; see the thesis of Pogrow [Pogrow-17]. Note that this family clearly contains all ordinary graphs.
Lower bound: The only known lower bound is for ordinary graphs, and shows that (for every $n$ and $\epsilon>1/\sqrt{n}$) there is a hypergraph $H$ with $\rank(H)=2$, such that every $(1+\epsilon)$-cut-sparsifier must have $\Omega(n/\epsilon^2)$ edges [AndoniCKQWZ-16]. A different, much simpler proof was devised by Carlson, Kolla, Srivastava, and Trevisan [CarlsonKST-17]. Thus, there is a large gap between the upper bound $O_\epsilon(n^2)$ and the lower bound $\Omega_\epsilon(n)$ (this notation omits dependence on $\epsilon$).
Remark: The above considers the number of hyperedges to be the size measure. An alternative measure is the total size of all hyperedges, i.e., $\sum_{e\in E} |e|$. The current upper bound on the total size of the sparsifier is $O_\epsilon(n^3)$, because every hyperedge has size at most $n$, and the lower bound is $\Omega_\epsilon(n)$ (coming from ordinary graphs), hence the gap here is even larger.
