Open Problems:91

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)$ [J. D. Batson, D. A. Spielman, and N. Srivastava. Twice-ramanujan sparsifiers. SIAM Review, 56(2):315334, 2014]. 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$ (this family clearly contains all ordinary graphs), see [Yosef Pogrow. Solving Symmetric Diagonally Dominant Linear Systems in Sublinear Time and Some Observations on Graph Sparsification. Weizmann MSc Thesis, 2017].

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]. For a simpler proof see [Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan: Optimal Lower Bounds for Sketching Graph Cuts. CoRR abs/1712.10261 (2017)]. 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 defines size as the number of edges. 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 sparisifier 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.